Submission #68756563

---

Source Code Expand

import bisect, heapq, sys, math, copy, itertools, decimal
from collections import defaultdict, deque
sys.setrecursionlimit(10**7)
def INT(): return int(input())
def MI(d=0): return map(lambda x:int(x)+d, input().split())
def MS(): return map(str, input().split())
def LI(d=0): return list(map(lambda x:int(x)+d, input().split()))
def LS(): return list(map(str, input().split()))
def pr_line(itr): print(*itr, sep='\n')
def pr_mtx(matrix): [print(*row) for row in matrix] 
dij = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dij2 = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
INF = float('inf')

H, W = MI()
A = [list(input()) for _ in range(H)]

visited = [[[INF, INF] for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == 'S':
            si, sj = i, j
        if A[i][j] == 'G':
            gi, gj = i, j

visited[si][sj][0] = 0
Q = deque()
Q.append((si, sj, 0))

while Q:
    i, j, k = Q.popleft()

    for di, dj in dij:
        ni, nj = i+di, j+dj
        if 0<=ni<H and 0<=nj<W and A[ni][nj] != '#':
            if k == 0:
                if A[ni][nj] in ('o', '.', 'S', 'G') and visited[ni][nj][k] == INF:
                    visited[ni][nj][k] = visited[i][j][k] + 1
                    Q.append((ni, nj, k))
                elif A[ni][nj] == '?' and visited[ni][nj][k^1] == INF:
                    visited[ni][nj][k^1] = visited[i][j][k] + 1
                    Q.append((ni, nj, k^1))
            else:
                if A[ni][nj] in ('x', '.', 'S','G')  and visited[ni][nj][k] == INF:
                    visited[ni][nj][k] = visited[i][j][k] + 1
                    Q.append((ni, nj, k))
                elif A[ni][nj] == '?' and visited[ni][nj][k^1] == INF:
                    visited[ni][nj][k^1] = visited[i][j][k] + 1
                    Q.append((ni, nj, k^1))

if min(visited[gi][gj]) != INF:
    print(min(visited[gi][gj]))
else:
    print(-1)

Submission Info

Judge Result