D - Grid Ice Floor Editorial by kyopro_friends
3乗解法公式で省略されている3乗解法を簡単に説明します。
「どのマスに止まっているか」を状態とし、上下左右どの方向に移動するかをDFS/BFSで探索します。その過程で通ったマスを記録します。
実装例(Python)
import sys
sys.setrecursionlimit(10**8)
N,M=map(int,input().split())
S=[input() for i in range(N)]
tomatta=[[False]*M for _ in range(N)]
tootta=[[False]*M for _ in range(N)]
def dfs(i,j):
tomatta[i][j]=True
# マス(i,j)に停止している状態から、上下左右への移動を調べる
for di,dj in [(0,1),(1,0),(0,-1),(-1,0)]:
ii,jj=i,j
while S[ii+di][jj+dj]!='#':
ii+=di
jj+=dj
tootta[ii][jj]=True
if not tomatta[ii][jj]:
dfs(ii,jj)
tootta[1][1]=True
dfs(1,1)
print(sum(sum(a) for a in tootta))
posted:
last update: