【寻找平面栅格图中的最短路径】

问题描述: 

小米在2021年8月10日发布了四足机器人CyberDog（铁蛋），现在如果有一张创建好的2维栅格地图，请你给铁蛋找一条从起点到终点的最短 路径，并输出最短路径的长度。 

如上图所示，0代表可以走的栅格，1代表禁止行走的栅格，铁蛋只能上下，左右行走，不可以走对角线。 为了方便编程，假设我们的地图都是正方形，而且我们起点总是在[0,0]左上角，终点总是在[n-1,n-1]右下角。

如上图所示我们会输出路径长度：9 当然如果没有通路，需要输出路径长度：-1 

输入描述: 

如上图所示，0代表可以走的栅格，1代表禁止行走的栅格，铁蛋只能上下，左右行走，不可以走对角线。 为了方便编程，假设我们的地图都是正方形，而且我们起点总是在[0,0]左上角，终点总是在[n-1,n-1]右下角。 

输出描述: 

如上图所示我们会输出路径长度：9 当然如果没有通路，需要输出路径长度：-1 

输入样例:

0 1 1 1 1  0 0 0 1 1  1 1 0 1 1  1 1 0 0 0  1 1 1 1 0 

输出样例: 9 

def lookuppath(grid):
    from collections  import deque
    col,row = len(grid[0]),len(grid)
    re = 0
    qu = deque()
    for i in range(row):
        for  j in range(col):
            if grid[i][j]==1:
                cursize = 0
                qu.append((i,j))
                grid[i][j]==1
               
                while len(qu) !=1:
                    front = qu.popleft()
                    cursize +=1
                    fr,fc = front[0],front[1]
                    
                    if fr-1 >=0 and fr -1  <= row-1 and grid[fr-1][fc]==0:
                        qu.append((fr-1,fc))
                        grid[fr-1][fr]=1
                    if fr + 1 >=1 and fr +1 <= row-1 and grid[fr+1][fc]==0:
                        qu.append((fr+1,fc))
                        grid[fr+1][fr]=1
                    if fc + 1 >=0 and fc +1 <= col-1 and grid[fr][fc+1]==0:
                        qu.append((fr,fc+1))
                        grid[fr][fc+1]=1
                    if fc-1 >=0 and fc-1 <= col-1 and grid[fr][fc-1]==0:
                        qu.append((fr,fc-1))
                        grid[fr][fc-1]=1
                re = max(re,cursize)
    return re
                    

51:19