import sys
input = sys.stdin.readline
from collections import *
dy = [0,0,-1,1]; dx = [-1,1,0,0]
def BFS(n,d):
visited = [[0]*M for i in range(N)]
dq = deque([(sy,sx,0)])
while dq:
y,x,cnt = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = 1
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and not visited[y1][x1]|board[y1][x1]:
if i==d:
if cnt < n:
dq.append((y1,x1,cnt+1))
else:
dq.appendleft((y1,x1,cnt))
return visited
N,M = map(int,input().split())
L,R = map(int,input().split())
board = [[*map(int,input().strip())] for i in range(N)]
for i in range(N):
for j in range(M):
if board[i][j]==2:
sy,sx = i,j; board[i][j] = 0
visitedL = BFS(L,0); visitedR = BFS(R,1)
print(sum([visitedL[i][j]&visitedR[i][j] for i in range(N) for j in range(M)]))
0-1 BFS를 이용하여 해결하였다.
풀이를 요약하면,
1. 좌 방향으로 L번 이동하여 도달할 수 있는 땅을 구한다. 이때 위,아래,우 방향에 대해서는 appendleft를 한다.
2. 우 방향으로 R번 이동하여 도달할 수 있는 땅을 구한다. 이때 위,아래,좌 방향에 대해서는 appendleft를 한다.
3. 1,2에서 도달한 땅에 대해서 두번 모두 도달할 수 있는 땅의 개수를 출력한다.
전구를 켜라 [백준 2423번] 전구를 켜라 (Python3) (tistory.com) 문제에서 처음 접한 0-1 BFS는 다양한 문제에서 활용할 수 있는 것 같다.
오늘의 교훈) 0-1 BFS는 유용하다.