Submission #9309853

---

Source Code Expand

from collections import deque

class GoalFound(Exception):
    def __init__(self, distance):
        self.distance = distance


class Solver:
    def __init__(self, H, W, N, maze) -> None:
        self.H = H
        self.W = W
        self.N = N
        self.maze = maze
        self.visited = set()
        self.queue = deque([])

    def find_start_pos(self):
        for h in range(self.H):
            for w in range(self.W):
                if self.maze[h][w] == 'S':
                    return (h, w)
        raise ValueError('Not found:{}'.format(obj))

    def lookup(self, pos):
        y, x = pos
        return self.maze[y][x]

    def breadth_first_search(self, pos, distance, life):
        y, x = pos
        if not (0 <= y < self.H):
            return
        if not (0 <= x < self.W):
            return
        if pos in self.visited:
            return

        tile = self.lookup(pos)
        if tile == "X":
            return
        if tile == str(life):
            if tile == str(self.N):
                raise GoalFound(distance)
            else:
                life += 1
                self.queue.clear()
                self.visited = set()

        self.visited.add(pos)
        self.queue.append(((y - 1, x), distance + 1, life))
        self.queue.append(((y, x - 1), distance + 1, life))
        self.queue.append(((y, x + 1), distance + 1, life))
        self.queue.append(((y + 1, x), distance + 1, life))

    def solve(self) -> int:
        self.queue.append((self.find_start_pos(), 0, 1))
        try:
            while len(self.queue) > 0:
                task = self.queue.popleft()
                self.breadth_first_search(*task)
        except GoalFound as e:
            return e.distance


if __name__ == "__main__":
    H, W, N = list(map(int, input().split()))
    maze = []
    for _ in range(H):
        maze.append(list(input()))

    s = Solver(H, W, N, maze)
    print(s.solve())

Submission Info

Judge Result