Backjun-グラフ(#2178)


https://www.acmicpc.net/problem/2178

Code

def bfs(i,j):
    queue = [[i,j]]
    while queue :
        x, y = queue[0]
        del queue[0]
        cnt = graph[x][y]+1
        if x > 0 and graph[x-1][y] == 1:
            graph[x-1][y] = cnt
            queue.append([x-1,y])
        if x < n-1 and graph[x+1][y] == 1:
            graph[x+1][y] = cnt
            queue.append([x+1,y])
        if y > 0 and graph[x][y-1] == 1:
            graph[x][y-1] = cnt
            queue.append([x,y-1])
        if y < m-1 and graph[x][y+1] == 1:
            graph[x][y+1] = cnt
            queue.append([x,y+1])

        if (x == n-2 and y == m-1) or (x == n-1 and y == m-2):
            break

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, list(input()))))

bfs(0,0)
print(graph[n-1][m-1])