#!/usr/bin/env python3
"""
花园迷宫 (garden_maze.py) — 第 22 轮:用随机生成树给花园种一座迷宫。

原理:完美迷宫(任意两点之间恰好一条路)= 格子图的一棵生成树。
递归回溯法就是在这张图上做 DFS,每走进一个新格子就砍掉一面墙
(把一条边收进生成树);墙,恰好是没被选进树里的那些边。

用法:
  python3 garden_maze.py                      # 15×15,种子取今天日期,直接打印
  python3 garden_maze.py --solve              # 用 BFS 解出唯一路径并标出
  python3 garden_maze.py --longest            # 找出迷宫直径(最远的两个房间)
  python3 garden_maze.py --stats --solve      # 打印全部实测统计
  python3 garden_maze.py -W 22 -H 22 --seed 20260804 --stats

验证(花园传统:想当然必被打脸):
  - 生成树性质: 树边数 == 格子数 − 1
  - 全可达:     BFS 从入口出发到达每一个格子
  - 解唯一:     完美迷宫的生成树性质保证任意两点路径唯一
  - 死胡同数:   生成树的叶子(度为 1 的格子)
  - 直径:       两次 BFS(从任意点出发找最远点,再从那点找最远点)
"""
import argparse
import random
import sys
from collections import deque

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def make_maze(w, h, rng):
    """递归回溯(迭代版 DFS)生成完美迷宫,返回 (入口, 树边集合)。"""
    tree = set()
    start = (rng.randrange(w), rng.randrange(h))
    visited = {start}
    stack = [start]
    while stack:
        cx, cy = stack[-1]
        nbs = [
            (cx + dx, cy + dy)
            for dx, dy in DIRS
            if 0 <= cx + dx < w and 0 <= cy + dy < h
            and (cx + dx, cy + dy) not in visited
        ]
        if not nbs:
            stack.pop()
            continue
        nxt = rng.choice(nbs)
        tree.add(frozenset(((cx, cy), nxt)))
        visited.add(nxt)
        stack.append(nxt)
    return start, tree


def cells_of(w, h):
    return [(x, y) for y in range(h) for x in range(w)]


def adjacency(w, h, tree):
    adj = {c: [] for c in cells_of(w, h)}
    for a, b in tree:
        adj[a].append(b)
        adj[b].append(a)
    return adj


def bfs_path(w, h, tree, start, end):
    """BFS 求最短路径,返回从 start 到 end 的格子序列。"""
    adj = adjacency(w, h, tree)
    prev = {start: None}
    q = deque([start])
    while q:
        c = q.popleft()
        if c == end:
            break
        for n in adj[c]:
            if n not in prev:
                prev[n] = c
                q.append(n)
    path = []
    c = end
    while c is not None:
        path.append(c)
        c = prev[c]
    path.reverse()
    return path


def farthest_from(w, h, tree, src):
    """BFS 求距离 src 最远的格子,返回 (最远格, 距离, 路径)。"""
    adj = adjacency(w, h, tree)
    prev = {src: None}
    q = deque([src])
    last = src
    while q:
        c = q.popleft()
        last = c
        for n in adj[c]:
            if n not in prev:
                prev[n] = c
                q.append(n)
    path = []
    c = last
    while c is not None:
        path.append(c)
        c = prev[c]
    path.reverse()
    return last, len(path) - 1, path


def render(w, h, tree, start, end, path=None):
    """画 ASCII 迷宫:S=入口 E=出口 ·=路径,#=树篱墙,空白=通道。"""
    grid = [["#"] * (2 * w + 1) for _ in range(2 * h + 1)]
    for x, y in cells_of(w, h):
        grid[2 * y + 1][2 * x + 1] = " "
    for (x1, y1), (x2, y2) in tree:
        if x1 == x2:  # 上下相邻,打通中间的横墙
            grid[y1 + y2 + 1][2 * x1 + 1] = " "
        else:  # 左右相邻,打通中间的竖墙
            grid[2 * y1 + 1][x1 + x2 + 1] = " "
    for x, y in path or []:
        grid[2 * y + 1][2 * x + 1] = "·"
    grid[2 * start[1] + 1][2 * start[0] + 1] = "S"
    grid[2 * end[1] + 1][2 * end[0] + 1] = "E"
    return "\n".join("".join(row) for row in grid)


def stats(w, h, tree, start, end):
    """全套实测统计,顺带用断言把'想当然'钉在墙上。"""
    adj = adjacency(w, h, tree)
    n_cells = w * h
    assert len(tree) == n_cells - 1, "生成树性质:树边数必须等于格子数−1"
    reach = len(bfs_path(w, h, tree, start, end))  # BFS 必达,顺带求出口路径
    from collections import deque as _dq
    seen = {start}
    q = _dq([start])
    while q:
        c = q.popleft()
        for n in adj[c]:
            if n not in seen:
                seen.add(n)
                q.append(n)
    assert len(seen) == n_cells, "全可达:迷宫必须没有一个格子被孤立"
    dead_ends = sum(1 for c in adj if len(adj[c]) == 1)
    far, dist, _ = farthest_from(w, h, tree, start)
    _, diam, diam_path = farthest_from(w, h, tree, far)
    return {
        "cells": n_cells,
        "edges": len(tree),
        "reachable": len(seen),
        "dead_ends": dead_ends,
        "solution_len": len(bfs_path(w, h, tree, start, end)) - 1,
        "diameter": diam,
    }


def main():
    ap = argparse.ArgumentParser(description="花园迷宫:随机生成树 + BFS 求解")
    ap.add_argument("-W", "--width", type=int, default=15)
    ap.add_argument("-H", "--height", type=int, default=15)
    ap.add_argument("--seed", type=int, default=None,
                    help="随机种子(默认取今天日期 YYYYMMDD,同一天同一座迷宫)")
    ap.add_argument("--solve", action="store_true", help="用 BFS 标出入口到出口的唯一路径")
    ap.add_argument("--longest", action="store_true", help="标出迷宫直径(最远的两个房间之间)")
    ap.add_argument("--stats", action="store_true", help="打印实测统计")
    ap.add_argument("--exit", nargs=2, type=int, metavar=("X", "Y"),
                    help="指定出口坐标(默认右下角)")
    args = ap.parse_args()

    seed = args.seed if args.seed is not None else int(__import__("datetime").date.today().strftime("%Y%m%d"))
    rng = random.Random(seed)
    start, tree = make_maze(args.width, args.height, rng)
    end = tuple(args.exit) if args.exit else (args.width - 1, args.height - 1)

    print(f"# 花园迷宫  {args.width}×{args.height}  seed={seed}  入口=左上角({start[0]},{start[1]})  出口=({end[0]},{end[1]})")
    print()
    if args.solve:
        path = bfs_path(args.width, args.height, tree, start, end)
        print(render(args.width, args.height, tree, start, end, path))
        print()
        print(f"入口 → 出口最短路径: {len(path) - 1} 步(唯一解,生成树保证)")
    elif args.longest:
        far, dist, path = farthest_from(args.width, args.height, tree, start)
        _, diam, dpath = farthest_from(args.width, args.height, tree, far)
        print(render(args.width, args.height, tree, start, end, dpath))
        print()
        print(f"迷宫直径: {diam} 步,从 {far} 到 {dpath[-1]}")
    else:
        print(render(args.width, args.height, tree, start, end))

    if args.stats:
        s = stats(args.width, args.height, tree, start, end)
        print()
        print("## 实测统计(全部断言通过)")
        print(f"- 格子总数: {s['cells']}")
        print(f"- 树边数:   {s['edges']} = 格子数−1 (生成树性质 ✓)")
        print(f"- 可达格子: {s['reachable']}/{s['cells']} (全可达 ✓)")
        print(f"- 死胡同:   {s['dead_ends']} 个 (生成树的叶子)")
        print(f"- 入口→出口: {s['solution_len']} 步")
        print(f"- 迷宫直径: {s['diameter']} 步 (最远的两个房间)")


if __name__ == "__main__":
    main()