import matplotlib.pyplot as plt
import numpy as np
import random
from collections import deque
# 20x20の論理マス（奇数行列の実体としては41x41）
rows, cols = 20, 20
maze = [[1 for _ in range(cols * 2 + 1)] for _ in range(rows * 2 + 1)]
# 迷路生成（DFS）
def carve(x, y):
maze[y][x] = 0
dirs = [(0, -2), (0, 2), (-2, 0), (2, 0)]
random.shuffle(dirs)
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 1 <= nx < cols * 2 and 1 <= ny < rows * 2 and maze[ny][nx] == 1:
maze[y + dy // 2][x + dx // 2] = 0
carve(nx, ny)
# スタートから生成
carve(1, 1)
maze[1][1] = 0
maze[rows * 2 - 1][cols * 2 - 1] = 0
start = (1, 1)
goal = (rows * 2 - 1, cols * 2 - 1)
# 幅優先探索（BFS）で最短経路探索
def bfs(maze, start, goal):
queue = deque([start])
visited = {start: None}
while queue:
current = queue.popleft()
if current == goal:
break
x, y = current
for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
nx, ny = x+dx, y+dy
if 0 <= nx < len(maze[0]) and 0 <= ny < len(maze):
if maze[ny][nx] == 0 and (nx, ny) not in visited:
queue.append((nx, ny))
visited[(nx, ny)] = current
# 経路復元
path = []
current = goal
while current:
path.append(current)
current = visited[current]
path.reverse()
return path
# 解く
path = bfs(maze, start, goal)
# 可視化
maze_array = np.array(maze)
plt.figure(figsize=(10, 10)) # サイズ拡大
plt.imshow(maze_array, cmap='Greys')
plt.xticks([]), plt.yticks([])
plt.title("20x20 Maze with Solved Path")
# 経路を赤で描画
if path:
px, py = zip(*path)
plt.plot(px, py, color='red', linewidth=1)
plt.show()