# Potřebujeme frontu, importujeme ji z knihoven Pythonu from collections import deque # Přečteme si šířku a výšku lesa tak, že rozdělíme první řádku podle mezer, # převedeme vzniklé řetězce do čísel a přiradíme je našim proměnným sirka, vyska = map(int, input().split()) # Přečteme si mapu lesa tak, že ze všech znaků na řádce uděláme seznam # a uděláme to pro všechny řádky, kterých by mělo být h mapa = [list(input()) for _ in range(vyska)] # Zkontrolujeme, zda jsou všechny řádky správně dlouhé for y in range(vyska): assert len(mapa[y]) == sirka, "Řádek je špatně dlouhý" # Definujeme si seznam všech možných kroků v mapě, v pořadí: # doprava, doleva, nahoru, dolů tahy = [(1, 0), (-1, 0), (0, 1), (0, -1)] # Prohledávání do šířky začínající na dvojici 'coord' # (pokud nevíš co prohledávání do šířky je, přečti si kuchařku o grafech) def bfs(coord): x, y = coord # Rozdělíme počáteční souřadnice na x a y fronta = deque([(x, y)]) # Vložíme je do fronty mapa[y][x] = '#' # Označíme si, že už jsme tu byli tak, že políčko "vyzdíme" pocetDostupnych = 1 # Minimálně začínající políčko je dostupné while(len(fronta) > 0): # Dokud není prázdná fronta x, y = fronta.popleft() # Vezmeme z ní první vrchol for (dx, dy) in tahy: # Vyzkoušíme všechny tahy po mapě noveX = x + dx noveY = y + dy # Pokud by nás nějaký zavedl mimo mapu, tak ho přeskočíme if noveX < 0 or noveY < 0 or noveX >= sirka or noveY >= vyska: continue # Pokud toto políčko je prázdné, je dosažitelné if mapa[noveY][noveX] == '.': mapa[noveY][noveX] = '#' # Označíme, abychom ho nezapočetli dvakrát pocetDostupnych += 1 # Započítáme ho fronta.append((noveX, noveY)) # Přidáme ho do fronty prohledávání return pocetDostupnych # Vrátíme počet dosažitelných políček # Nalezneme políčko s Petrem a Sárou # mělo by být v souradnicePetra[0] jako první prvek seznamu coord souradnicePetra = [(x, y) for x in range(sirka) for y in range(vyska) if mapa[y][x] == 'P'] # Pokud je v mapě špatný počet Petrů, budeme si stěžovat assert len(souradnicePetra) >= 1, "Mapa neobsahuje Petra" assert len(souradnicePetra) <= 1, "Mapa obsahuje více Petrů" # Vypíšeme počet dosažitelných políček na výstup print(bfs(souradnicePetra[0]))