from collections import deque
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
h, w, sr, sc, fr, fc = map(int, input().split())
check = [[-1] * m for _ in range(n)]
wall = deque()
for i in range(n):
for j in range(m):
if g[i][j] == 1:
wall.append((i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
q.append((sr-1, sc-1))
check[sr-1][sc-1] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m :
continue
if nx + h -1 < 0 or ny + w -1 < 0 or nx + h -1 >= n or ny + w -1 >= m :
continue
go = True
for u, v in wall:
if nx <= u < nx + h and ny <= v < ny + w:
go = False
if go == True and check[nx][ny] == -1:
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
print(check[fr-1][fc-1])
벽을 모두 큐에 넣고 탐색 (pypy제출)
from collections import deque
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
h, w, sr, sc, fr, fc = map(int, input().split())
check = [[-1] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
q.append((sr-1, sc-1))
check[sr-1][sc-1] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m :
continue
if nx + h -1 < 0 or ny + w -1 < 0 or nx + h -1 >= n or ny + w -1 >= m :
continue
go = True
if i == 0:
for u in range(ny, ny + w):
if g[nx][u] == 1:
go = False
break
elif i == 1:
for u in range(ny, ny + w):
if g[nx + h- 1][u] == 1:
go = False
break
elif i == 2:
for u in range(nx, nx + h):
if g[u][ny] == 1:
go = False
break
elif i == 3:
for u in range(nx, nx + h):
if g[u][ny + w - 1] == 1:
go = False
break
if go == True and check[nx][ny] == -1:
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
print(check[fr-1][fc-1])
경계부분만 벽이 있는지 탐색하였다. 시간이 줄어들음.(pypy 제출)
python3 는...?