迷路最短経路

maze-problem.py

# https://yosh.hateblo.jp/entries/2010/01/19#p1
# http://okajima.air-nifty.com/b/2010/01/post-abc6.html

from dataclasses import dataclass
from typing import NamedTuple, TextIO
from io import StringIO

class Point(NamedTuple):
    x: int
    y: int


class Edge(NamedTuple):
    head: Point
    tail: Point


def neighbours(point: Point) -> list[Point]:
    x, y = point
    return [Point(x, y - 1), Point(x, y + 1), Point(x - 1, y), Point(x + 1, y)]


# This function returns new visited edges and REMOVE new visited points from `unvisited`.
def access(unvisited: set[Point], edges: list[Edge]) -> list[Edge]:
    new_visited = []
    for (_, tail) in edges:
        for point in neighbours(tail):
            if point in unvisited:
                new_visited.append(Edge(tail, point))
                unvisited.remove(point)
    return new_visited


@dataclass
class Board:
    blanks: set[Point]
    start: Point
    goal: Point
    points: list[list[str]]

def load_board(f: TextIO):
    blanks = set()
    start = Point(-1, -1)
    goal = Point(-1, -1)
    points = []
    for y, line in enumerate(f):
        for x, ch in enumerate(line):
            if ch == ' ':
                blanks.add(Point(x, y))
            if ch == 'S':
                start = Point(x, y)
            if ch == 'G':
                goal = Point(x, y)
        points.append(list(line.rstrip('\n')))
    return Board(blanks, start, goal, points)


def main():
    board_str = '''\
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************'''
    board = load_board(StringIO(board_str))
    unvisited = board.blanks | {board.goal}
    new_edges = [Edge(board.start, board.start)]
    segments = {}
    while (new_edges := access(unvisited, new_edges)):
        segments.update({e.tail: e.head for e in new_edges})
    target = board.goal
    while target != board.start:
        target = segments[target]
        board.points[target.y][target.x] = '$'
    board.points[board.start.y][board.start.x] = 'S'
    for line in board.points:
        print(''.join(line))

if __name__ == '__main__':
    main()