盲目搜索之宽度优先搜索算法Solution for https://pad.251.sh/s/jcS1ea2t5

maze.py

# -*- coding:utf-8 -*-
# Problem: https://pad.251.sh/s/jcS1ea2t5
# Author: Kujo Ryoka

from unittest import TestCase


class Maze:
    def __init__(self, map, n, m, x, y):
        self.ans = 0  # 最短步长结果
        self.map = map  # 迷宫地图map[0,n-1][0,m-1]（下标0开始）
        self.n = n  # 迷宫地图行数n
        self.m = m  # 迷宫地图列数m
        self.x = x  # 起点，行坐标（下标0开始）
        self.y = y  # 起点，列坐标（下标0开始）


class Solution:

    def solveMaze(self, maze):
        """求解迷宫问题

        :type: maze: class Maze #迷宫的数据结构类
        :rtype: maze.ans: int   #返回最短路径长度
        """

        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        been_to = [[False, ] * maze.m for _ in range(maze.n)]
        """ 去过的地点 
        使用数组实现O(1)访问和更新
        也可以使用set((x, y),)实现
        """

        about_to = []
        """ 待访问的坐标 由 (x, y, step) 构成
        x为行号，y为列号，step是当前步数
        """

        about_to += (maze.x, maze.y, 0),
        """ 添加起始位置 """

        while about_to:
            go_x, go_y, step = about_to.pop(0)
            if maze.map[go_x][go_y] == 0:
                # 不是路
                continue
            if go_x in (0, maze.n - 1) or go_y in (0, maze.m - 1):
                # 到达边界
                maze.ans = step
                break
            if been_to[go_x][go_y]:
                # 来过了
                continue
            been_to[go_x][go_y] = True
            about_to += (
                (go_x + 1, go_y, step + 1),
                (go_x - 1, go_y, step + 1),
                (go_x, go_y + 1, step + 1),
                (go_x, go_y - 1, step + 1))
        else:
            maze.ans = 0
        return maze.ans

    # ********** End **********#


class TestSolution(TestCase):
    def test_solve_maze(self):
        maze = Maze(
            (
                (0, 1, 0, 1),
                (0, 1, 1, 1),
                (1, 1, 0, 0),
                (0, 1, 0, 1),
            ),
            4, 4,
            2, 1
        )
        Solution().solveMaze(maze)
        self.assertEqual(maze.ans, 1)

    def test_no_answer(self):
        maze = Maze(
            (
                (0, 0, 0, 0),
                (0, 1, 1, 0),
                (0, 1, 0, 0),
                (0, 0, 0, 0),
            ),
            4, 4,
            2, 1
        )
        Solution().solveMaze(maze)
        self.assertEqual(maze.ans, 0)

    def test_large(self):
        maze = Maze(
            (
                (0, 1, 0, 0, 0, 0, 1),
                (0, 1, 1, 1, 0, 0, 1),
                (0, 1, 0, 0, 0, 0, 1),
                (0, 1, 1, 1, 1, 0, 1),
                (0, 1, 0, 0, 1, 0, 1),
                (0, 1, 0, 0, 0, 0, 1),
            ),
            6, 7,
            3, 2
        )
        Solution().solveMaze(maze)
        self.assertEqual(maze.ans, 3)


if __name__ == '__main__':
    """
    Try input:

    4 4
    0 1 0 1
    0 1 1 1
    1 1 0 0
    0 1 0 1
    2 1
    """

    n, m = map(int, input().split())
    m_map = tuple(tuple(map(int, input().split()))[:m] for _ in range(n))
    x, y = map(int, input().split())
    maze = Maze(m_map, n, m, x, y)
    Solution().solveMaze(maze)
    print(maze.ans)