题解 | #迷宫问题#

尝试在回溯时处理死路情况，主要实现参考下面代码https://blog.nowcoder.net/n/478eaf14b4b246ac9d6d31f313493690

while True:
    try:
        row, col = [int(x) for x in input().split(' ')]
        maze = []
        for i in range(row):
                maze.append([int(x) for x in input().split(' ')])
        #按行分割数据构建迷宫 
        
        lst = [(0,0)]#路径点
        while lst:
            if lst[-1] == (row-1, col-1):#终点判断
                for i in lst:
                    print('(%d,%d)'%(i))
                break
            i, j = lst[-1]#未到终点回溯一步
            maze[i][j] = 2#标记走过点
            
            count = 0#有效路径点计数
            check = []#有效路径内容统计
            if i-1>=0:
                count +=1
                check.append(maze[i-1][j])
            if i+1<row:
                count +=1
                check.append(maze[i+1][j])
                
            if j-1>=0:
                count +=1   
                check.append(maze[i][j-1])
            if j+1<col:
                count +=1
                check.append(maze[i][j+1])
            
            wall_walked = check.count(2) + check.count(1)
            #存在的0已经走过，且该0是除2外唯一0，则继续回溯
            if( wall_walked == count):
                lst.pop()
                i, j = lst[-1]#未到终点回溯一步
                maze[i][j] = 2#标记走过点
                
                
            if i-1 >= 0 and maze[i-1][j] == 0:#
                lst.append((i - 1, j))
                continue
            elif i+1 < row and maze[i+1][j] == 0:
                lst.append((i + 1, j))
                continue   
            elif j+1 < col and maze[i][j+1] == 0:
                lst.append((i, j+1))
                continue   
            elif j-1 >= 0 and maze[i][j - 1]==0:
                lst.append((i, j - 1))
                continue
            else:
                 lst.pop()
        else:
            print('This is a maza that can not be finished')
    except:
        break