問題描述
給定一張城市地圖：E（≤40）條東西向街道，N（≤30）條南北向街道。地圖以字符網格表示：'+' 為路口，'-' 和 '|' 為道路，'.' 為建築/障礙。起點 'S'、終點 'E'。需輸出最短路徑的導航指令，每條指令為方向 (N/E/S/W) + 街區數。最短路徑保證存在且唯一。
解題步驟
- 解析地圖構建圖：掃描網格，將每個路口 '+' 編號，根據 '-' 和 '|' 添加邊（權重 1 街區）。
- BFS 求最短路：從 S 到 E，無權圖用 BFS 即可，記錄前驅節點與方向。
- 路徑壓縮生成指令：回溯得到節點序列，合併連續同方向步數，輸出指令。
關鍵細節
- 輸入格式：2N 行，每行 2E-1 字符，奇數行為東西向街道（含 '+', '-', 'S', 'E'），偶數行為南北向街道（含 '|', '.', 空格）；
- 坐標映射：路口行索引 0,2,4... 對應 N 行，列索引 0,2,4... 對應 E 列；
- 唯一性保證：BFS 時若遇到同距離多前驅，按方向優先級（如 N
樣例解析
輸入 3×6 地圖，輸出 9 條指令，完美匹配樣例輸出。
參考實現
完整代碼：Bubuko 博客
