#!/usr/bin/python3 # Načtení vstupu: R, S = map(int, input().split()) # Načteme si jednotlivé řádky jako jako stringy do pole. Abychom mohli jednotlivá # políčka i měnit, tak ještě převedeme jednotlivé řádky na pole pomocí list(). # Pak můžeme indexovat mapa[R][S]. mapa = [list(input()) for _ in range(R)] # Funkce na nalezení jednoho pruhu: def najdi_pruh(mapa, oznaceni_pruhu): # Začneme vždy na prvním řádku a budeme postupovat dolů # 1. Najdeme první volné políčko if mapa[0].count('.') == 0: return False # Žádné volné políčko na prvním řádku již není s = mapa[0].index('.') # 2. Na každém řádku najdeme nejlevější místo, kde můžeme sestoupit na další řádek for r in range(R): # 2.1 Zkontrolujeme současné políčko a případně skončíme if mapa[r][s] != '.': return False # 2.2 Označíme toto políčko za použité, pokud jsme právě došli na poslední # řádek, tak jsme vyhráli mapa[r][s] = oznaceni_pruhu if r == R-1: return True # 2.3 Nejdříve zajedeme co nejvíce doleva while s - 1 >= 0 and mapa[r][s-1] == '.': s -= 1 mapa[r][s] = oznaceni_pruhu # 2.4 Pak najdeme první místo, kde se dá sestoupit dolů # (posouváme se doprava - i po vlastních stopách - než najdeme dole .) while mapa[r+1][s] != '.' and s + 1 < S and (mapa[r][s+1] == '.' or mapa[r][s+1] == oznaceni_pruhu): s += 1 mapa[r][s] = oznaceni_pruhu # Teď bychom měli stát nad prázdným políčkem (a nebo jsme dojeli až # na konec řádku, nic nenašli a algoritmus selže v dalším kroku) # 3. Postupně S-krát spustíme funkci výše (více pruhů tam ani být nemůže) nalezenych_pruhu = 0 for i in range(S): if najdi_pruh(mapa, i): nalezenych_pruhu +=1 else: break print(nalezenych_pruhu) # 4. Debug - vypsání mapy po nalezení všech pruhů #for r in range(R): # print("".join(map(str, mapa[r])))