综合项目：森林消防指挥系统

# 综合项目：森林消防指挥系统（树 + BFS + 哈夫曼）
from collections import deque
import heapq

# 模块一：指挥树——命令从总队一层层下发（完全二叉树数组表示）
team = ["", "总队", "一分队", "二分队", "三小队", "四小队", "五小队", "六小队"]
print("== ① 指挥链 ==")
for i in range(1, len(team)):
    if i == 1:
        print(team[i], "发布命令")
    else:
        print(team[i], "听令于", team[i // 2])

# 模块二：救援最短路——从消防站 S 到火点 E（BFS 逐层扩散）
forest = [
    "S..#",
    "##.#",
    "...#",
    ".#..",
    ".##E",
]
rows = len(forest)
cols = len(forest[0])
dist = [[-1] * cols for _ in range(rows)]
dist[0][0] = 0
queue = deque([(0, 0)])
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
    r, c = queue.popleft()
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            if forest[nr][nc] != "#" and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
print("== ② 救援路线 ==")
print("消防站到火点最少", dist[4][3], "步，立刻派最近的分队出发！")

# 模块三：电台报文压缩——字数统计后做哈夫曼合并
freq = {"火": 5, "风": 2, "水": 2, "撤": 1, "援": 1}
heap = []
for ch, w in freq.items():
    heapq.heappush(heap, (w, ch))
total = 0
while len(heap) > 1:
    w1, c1 = heapq.heappop(heap)
    w2, c2 = heapq.heappop(heap)
    total = total + w1 + w2
    heapq.heappush(heap, (w1 + w2, c1 + c2))
print("== ③ 报文压缩 ==")
print("这条", sum(freq.values()), "字的报文，哈夫曼编码后只要", total, "比特")