题目： 输入一个二维数组，1表示不可走，0表示可走，通路是从左上角往右下角找，右下角是出口。要求找到路径最短的走法，且优先级为下左上右，若发现步数一致的走法，则按照字典序对步数结果进行排序。
该迷宫为：
0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1
0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1
0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1
0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0
0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1
1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1
1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1
1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0
1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0
1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1
0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1
1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0
0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0
0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1
1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1
1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0
我们使用的方法是BFS也就是广度优先搜索。广度优先搜索需要利用队列来解决问题，其思想就是，从某点开始，探索一系列可以走的点，然后再继续从这些点开始，找到更多能走的点，最后达到我们所要完成的目标，点的不重复问题，以及先后顺序问题是非常值得注意的，本题的思想就是从入口出发，然后依次通过BFS找到可以走的点，然后将他们存放到队列中，依次走，去掉重复点，然后通过不断的循环，可以找到最快的路径，也可以利用特定的排序来决定他的走步的先后顺序，非常巧妙，此题应该还有多解，以后更新。实现算法明天手打。
#程序来自CSDN的一个大佬，我只是学习之后自己默写了一遍
#来保存小孩在迷宫中的位置，包含三个元素，一个是横坐标，一个是纵坐标，一个是已经走过的步数以及路线
class Node(object):
def __init__(self,x,y,w):
self.x = x
self.y = y
self.w = w
def __str__(self):
return self.w
def up(node):
return Node(node.x-1,node.y,node.w+'U')
def down(node):
return Node(node.x+1,node.y,node.w+'D')
def left(node):
return Node(node.x,node.y-1,node.w+'L')
def right(node):
return Node(node.x,node.y+1,node.w+'R')
#这句if的意思是指只在本文件运行时才会进行执行，__name__在本文件直接执行时，他的值为文件的名称包含后缀，
#而当本文件以import的方式进行引用时，__name__的值为文件的名称不包含后缀，而__main__始终指向文件的名称
#包含后缀。所以达到了直接运行时执行以下的内容，但是作为包import到其他项目中去，if判断为False，所以不
#执行
if __name__ == "__main__":
#第一步，初步准备
m,n = map(int,input().split()) #map是python中的内置函数，map(function,iterable),对于每个数据都执行function，返回一个迭代器
visited = set() #建立一个集合，来存储已经走过的位置，建立集合是因为集合具有不可重复性，在BFS中，有可能发生探索过程中往回走的情况，要通过这种方式进行杜绝
queue = [] #建立一个队列，建立队列是因为要进行广度探索，所以要记住每一次走过的点，以及下一次要走的点，这个队列可以对走点的先后顺序进行保证，同时保证广度搜索不会丢点
#第二步，输入数据
map_int = [[0]*(n+1)]#因为迷宫是要从1,1为起点的，所以要在上方建立一排0，和左边建立一排0，这样开始的点就可以为1,1了
#map_int的格式问题：因为我们要做的是二维迷宫，所以我们选择使用二维数组，每一行是一个数组，因为在python中input的类型是str，所以要编入数组还需要进行类型转换
for i in range(1,m+1):
map_int.append([0]*(n+1))#加入一行元素，个数与迷宫一行数字的个数相同，达到占位的效果
nums = input()#输入迷宫数据，按照行输入，不必有空格
nums = '0' + nums#如之前所说，迷宫要从1,1,开始走，所以左方也要加一排0站位
for j in range(0,n+1):
map_int[i][j] = ord(nums[j]) - 48 #ord为python中的内置函数以一个字符为对象，返回他的ASCII码值，本程序使用这种方法将str转换为字符串
node = Node(1,1,"") #创建第一个节点
queue.append(node) #将节点放入到队列之中
#第三步，进行正式的迷宫广度搜索
while len(queue) != 0:
movenode = queue[0] #将队列中第一个节点开始移动
queue.pop(0) #降低一个节点移出队列
movestr = str(movenode.x)+" "+str(movenode.y)#将节点所移动到的位置记录下来，以防止队列将走过相同的节点
if movestr not in visited:
visited.add(movestr) #将节点加入到集合中，然后通过结合来对是否以后节点进行判断，如果已经存在在集合中，则不再加入队列
#如果满足条件，则对节点进行广度搜索，找到他能走到的符合规则的下一个点
if movenode.x ==m and movenode.y ==n:#判断是否已经走到了终点，若走到终点，因为我们只是找最短路径，第一个到终点的一定是步数最少的，所以我们可以直接break
print(movenode.w)
break
#因为题目中要求，同样步数时，按照字典序进行优先级划分，所以我们在进行广度探索时，也按照字典序作为优先级进行遍历，即为D>L>R>U
if movenode.x<m:#向下
if map_int[movenode.x+1][movenode.y] ==0:
queue.append(down(movenode))
if movenode.y>1:#向左
if map_int[movenode.x][movenode.y-1] ==0:
queue.append(left(movenode))
if movenode.y<n:#向右
if map_int[movenode.x][movenode.y+1] ==0:
queue.append(right(movenode))
if movenode.x>1:#向上
if map_int[movenode.x-1][movenode.y] ==0:
queue.append(up(movenode))
