学霸的迷宫--python实现--蓝桥杯--BFS

题目描述

学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。

输入

第一行两个整数n， m，为迷宫的长宽。
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出

第一行一个数为需要的最少步数K。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

样例输入

3 3
001
100
110

样例输出

4
RDRD

题目分析

以上面例子为例，先做成地图数组


每一个步骤都有下左右上四个选择，做成四个函数若符合条件则调用并返回一个新的节点存入队列之中，并把访问过的点存进set减去不必要的枝节。直到找到终点则退出

代码实现

class Node:
    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, node.y - 1, node.w+"U")	//上的情况


def down(node):
    return Node(node.x, node.y + 1, node.w+"D")	//下的情况


def left(node):
    return Node(node.x - 1, node.y, node.w+"L")	//左的情况


def right(node):
    return Node(node.x + 1, node.y, node.w+"R")	//右的情况


if __name__ == '__main__':
    n, m = map(int, input().split())
    visited = set()			//记录访问过的点
    queue = []				
    map_int = [[0] * (m + 1)]
    for i in range(1, n+1):
        map_int.append([0]*(m+1))
        nums = input()
        nums = "0" + nums
        for j in range(0, m+1):
            map_int[i][j] = ord(nums[j]) - 48	//ord转化为ascII码
    node = Node(1, 1, "")			//设置起点
    queue.append(node)
    while len(queue) != 0:
        moveNode = queue[0]			//设置当前移动点为moveNode
        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:			//若到达终点则输出且退出循环
                print(len(moveNode.__str__()))				//步数
                print(moveNode)								//打印路径
                break
            if moveNode.y < n:								//首先顺序为下
                if map_int[moveNode.y + 1][moveNode.x] == 0:
                    queue.append(down(moveNode))
            if moveNode.x > 1:								//第二顺序是左
                if map_int[moveNode.y][moveNode.x - 1] == 0:
                    queue.append(left(moveNode))
            if moveNode.x < m:								//第三顺序是右
                if map_int[moveNode.y][moveNode.x + 1] == 0:
                    queue.append(right(moveNode))
            if moveNode.y > 1:								//最后顺序是上
                if map_int[moveNode.y - 1][moveNode.x] == 0:
                    queue.append(up(moveNode))