題意#
給你一張迷宮的地圖，你的任務是找出一條從起點（A）走到終點（B）的路徑。
迷宮的格式跟前一題非常類似，是一張 \(n \times m\) 的網格圖，有可以走的地板（.）跟不能穿越的牆壁（#）。你只能夠上下左右移動。
如果可以走到終點，要先輸出 YES，接著輸出最短路徑的長度，最後再印出具體走法路徑（由 L、R、U、D 字元組成的字串）。如果有好幾組解，給出其中任意一種都可以。如果根本走不到終點，輸出 NO 就好。
思路#
這題不只是要判斷能不能走到終點，還要給出「最少步數」的走法。一講到網格圖上的最短路徑，我們的第一直覺就要想到廣度優先搜尋（BFS）。
我們可以將起點推入佇列（Queue），然後開始一層一層地向外擴展。因為 BFS 就像是在同心圓水波一樣擴散找點，所以當我們第一時間碰到終點的那個瞬間，這條路徑保證就是最短的。
這題最難的地方其實不是 BFS 本身，而是「如何回溯路徑」。我們可以準備兩個陣列來記錄資訊：
- 一個用來記錄「每個點是從哪個點走過來的」（可以用座標的一維化
x * m + y來存）。 - 另一個用來記錄「走到這個點的最後一步是哪個方向」（例如向右走就是
R）。
有了這兩個資訊，當我們走到終點時，只要不斷往回追溯「從哪裡來」以及「用什麼方向到達」，收集這些方向字串後再把它反轉（Reverse），就能得到從起點出發的正確走法了。如果整個 BFS 都跑完了終點還是沒有被更新，那就代表無解。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// 上下左右四個方向的位移陣列，與題目所需的 RLUD 對應
vector<int> mx = {0, 1, 0, -1}, my = {1, 0, -1, 0};
string dir = "RDLU";
int n, m, sx, sy, ex, ey, cnt = 0;
vector<vector<char>> v;
vector<vector<int>> vis;
// 此題主要使用 BFS，這邊的 DFS 未使用到
void dfs(int x, int y) {
vis[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x+mx[i], ny = y+my[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && v[nx][ny] != '#' && !vis[nx][ny]) dfs(nx, ny);
}
}
signed main() { WA();
cin >> n >> m;
v.assign(n, vector<char>(m));
vis.assign(n, vector<int>(m));
// 讀入迷宮，同時記錄起點 A 與終點 B 的座標
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
cin >> v[i][j];
if (v[i][j] == 'A') sx = i, sy = j;
if (v[i][j] == 'B') ex = i, ey = j;
}
string ans;
queue<tuple<int, int>> q;
vector<int> mp(n*m); // 紀錄來源座標，以此建立反向指標 (Parent tree)
vector<char> go(n*m); // 紀錄到達此格時所採取的方向字元
q.push({sx, sy});
while (q.size()) {
auto [x, y] = q.front(); q.pop();
if (ex == x && ey == y) {
break; // 找到終點，提早結束 BFS
}
if (vis[x][y]) continue;
vis[x][y] = 1; // 標記為已造訪
// 嘗試往四個方向擴展
for (int i = 0; i < 4; i++) {
int nx = x+mx[i], ny = y+my[i];
// 確認有無撞牆與邊界
if (nx >= 0 && nx < n && ny >= 0 && ny < m && v[nx][ny] != '#' && !vis[nx][ny]) {
q.push({nx, ny});
// 將 2D 座標壓縮為 1D 進行來源與方向的儲存
mp[nx*m+ny] = x*m+y;
go[nx*m+ny] = dir[i]; // 依賴全域的陣列判斷方向對應字元
}
}
}
int now = ex*m+ey;
// 如果終點的來源指標為 0（且非起點本身），代表終點無法到達
if (!mp[now]) return cout << "NO\n", 0;
// 從終點往回回溯，還原出路徑字串
while (mp[now] != sx*m+sy) {
ans += go[now];
now = mp[now];
}
ans += go[now];
// 因為從終點尋找，路徑是反的，所以要從尾端顛倒過來印
cout << "YES\n" << ans.size() << '\n' << string(ans.rbegin(), ans.rend()) << '\n';
}
