from collections import deque import sys def main() -> None: sys.setrecursionlimit(1 << 25) input_data = sys.stdin.read().rstrip().splitlines() it = iter(input_data) H, W = map(int, next(it).split()) Sy, Sx = map(int, next(it).split()) # 行, 列(1-indexed) Gy, Gx = map(int, next(it).split()) # 行, 列(1-indexed) Sy -= 1; Sx -= 1 Gy -= 1; Gx -= 1 grid = [list(next(it)) for _ in range(H)] DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)] MASKS = [1 << i for i in range(4)] INF = -1 dist = [[[INF] * 16 for _ in range(W)] for _ in range(H)] dq = deque() start_state = 0 dist[Sy][Sx][start_state] = 0 dq.append((Sy, Sx, start_state)) while dq: y, x, state = dq.popleft() d_now = dist[y][x][state] if (y, x) == (Gy, Gx) and state == 0: print(d_now) return for k, (dy, dx) in enumerate(DIRS): ny, nx = y + dy, x + dx if 0 <= ny < H and 0 <= nx < W and grid[ny][nx] != '#': nstate = state ^ MASKS[k] # 対応するビットを反転 if dist[ny][nx][nstate] == INF: dist[ny][nx][nstate] = d_now + 1 dq.append((ny, nx, nstate)) print(-1) if __name__ == "__main__": main()