算法流程

1. 讀取地圖，記錄起點、K 個機關座標（按順序）。
2. 依次 BFS 從當前位置到下一機關：

• BFS 狀態：(x,y,step)，訪問標記 vis[x][y]。
• 擴展 8 方向，合法性檢查含「夾角限制」。
• 到達目標機關座標返回步數，並將該機關格標記為空地（'.'），作為下一輪 BFS 起點。

關鍵代碼

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 110;
const int INF = 0x3f3f3f3f;
int N, M, K;
char g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dr[8] = {-1,-1,-1,0,0,1,1,1};
int dc[8] = {-1,0,1,-1,1,-1,0,1};

struct Node { int r, c, d; };

bool valid(int r, int c) {
    return r>=1 && r<=N && c>=1 && c<=M && !vis[r][c] && g[r][c]!='#';
}

bool can_move(int r, int c, int nr, int nc) {
    if (abs(r-nr)+abs(c-nc) == 1) return true; // 直向
    // 斜向：檢查兩側直向格
    int cnt = 0;
    if (g[r][nc] == '#') ++cnt;
    if (g[nr][c] == '#') ++cnt;
    return cnt < 2;
}

int bfs(int sr, int sc, int tr, int tc) {
    if (sr==tr && sc==tc) return 0;
    memset(vis, 0, sizeof(vis));
    queue q;
    q.push({sr, sc, 0});
    vis[sr][sc] = true;
    while (!q.empty()) {
        Node u = q.front(); q.pop();
        for (int i=0;i<8;++i) {
            int nr=u.r+dr[i], nc=u.c+dc[i];
            if (!valid(nr,nc) || !can_move(u.r,u.c,nr,nc)) continue;
            if (nr==tr && nc==tc) return u.d+1;
            vis[nr][nc] = true;
            q.push({nr, nc, u.d+1});
        }
    }
    return -INF;
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> N >> M >> K;
        for (int i=1;i<=N;++i) cin >> (g[i]+1);
        int sr, sc; cin >> sr >> sc;
        vector> targets;
        for (int i=0;i> r >> c;
            targets.emplace_back(r,c);
            g[r][c] = '@'; // 標記機關
        }
        
        int ans = 0;
        bool ok = true;
        for (auto [tr,tc] : targets) {
            g[tr][tc] = '.'; // 觸發後變空地
            int dist = bfs(sr, sc, tr, tc);
            if (dist < 0) { ok = false; break; }
            ans += dist;
            sr = tr; sc = tc;
        }
        cout << (ok ? ans : -1) << '\n';
    }
    return 0;
}

關鍵細節

1. 機關觸發後變空地：g[tr][tc]='.'，允許後續路徑經過。
2. 起點可能在機關上：題目提示「坑是起點為第二個或以後的機關上」。代碼中 BFS 起始檢查 sr==tr && sc==tc 返回 0 步完美處理。
3. 夾角判斷：can_move 只檢查水平/垂直相鄰兩格，不檢查對角對面格。
4. 多測試用例：每案例重置地圖、訪問標記。

複雜度

• 單次 BFS：O(NM) ≤ 10000。
• K ≤ 10 段，總時間 ≤ 10×10000 = 100k，極快。
• 空間：O(NM)。

總結

ZZULIOJ 1726 是「多目標順序 BFS + 8方向移動 + 幾何通行約束」綜合題。關鍵點：

1. 將問題分解為 K+1 個獨立的單源單汇最短路。
2. BFS 狀態簡單，合法性判斷封裝為 can_move。
3. 機關觸發後地圖動態更新（變空地）。
4. 起點在機關上的邊界處理。

掌握「BFS + 動態障礙 + 移動約束」模板，可解決所有網格最短路變體。