题目描述

给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。

最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式
第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤100

样例

输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8

算法1

bfs

python 代码

import collections

def bfs():
    q=collections.deque()
    q.append((0,0))
    d=[[-1]*m for _ in range(n)]
    directions = [(-1,0),(0,1),(1,0),(0,-1)]        #上右下左
    d[0][0]=0
    while q:
        h,t=q.popleft()         #取出队头并删掉
        for x,y in directions:
            new_h = h+x
            new_t = t+y
            if new_h>=0 and new_h<n and new_t>=0 and new_t<m and g[new_h][new_t]==0 and d[new_h][new_t]==-1:
            #判断上下左右移动的时候不出界，要移动到的位置不是墙，且没有走过
                d[new_h][new_t] = d[h][t]+1
                q.append((new_h,new_t))
    return d[-1][-1]



if __name__ == "__main__":
    n,m = map(int,input().split())
    N = 110
    g = []
    for i in range(n):
        g.append(list(map(int,input().split())))
    print(bfs())