HDU 2579 Dating with girls (2)：BFS + 狀態壓縮（時間維度）

問題描述

迷宮中有石頭（#）、起點（Y）、終點（G）。石頭在時間為 k 的倍數時不可通行，其他時間可通行。求從 Y 到 G 的最短時間，不可到達輸出 "Please give me another chance!"。迷宮大小 ≤ 100×100，k ≤ 10。多測試用例。

核心思路：三維 BFS

狀態：(x, y, t_mod_k)，其中 t_mod_k = 當前時間 % k。因為石頭通行性只依賴 t % k，且 k ≤ 10，狀態空間 ≤ 100×100×10 = 10⁵，BFS 完全可行。
注意：可以回頭走（即允許重複訪問同一格子但時間模不同），所以 vis 必須是三維的。

狀態轉移

• 從 (x, y, tm) 向四個方向嘗試移動，新時間 nt = tm + 1，新模 nmod = nt % k。
• 目標格子 (nx, ny) 若為石頭（#）且 nmod != 0，不可通行。
• 若 vis[nx][ny][nmod] 未訪問，入隊。
• 到達 G 即返回當前時間 nt。

代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
char grid[MAXN][MAXN];
bool vis[MAXN][MAXN][11];
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};

struct Node { int x, y, step; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, m, k; cin >> n >> m >> k;
        Node start, goal;
        for (int i = 0; i < n; ++i) {
            cin >> grid[i];
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 'Y') start = {i, j, 0};
                else if (grid[i][j] == 'G') goal = {i, j, 0};
            }
        }
        memset(vis, 0, sizeof(vis));
        queue<Node> q;
        q.push(start);
        vis[start.x][start.y][0] = true;
        bool found = false;
        while (!q.empty()) {
            Node cur = q.front(); q.pop();
            if (cur.x == goal.x && cur.y == goal.y) {
                cout << cur.step << '\n';
                found = true;
                break;
            }
            for (int dir = 0; dir < 4; ++dir) {
                int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
                int nstep = cur.step + 1;
                int nmod = nstep % k;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (vis[nx][ny][nmod]) continue;
                if (grid[nx][ny] == '#' && nmod != 0) continue;
                vis[nx][ny][nmod] = true;
                q.push({nx, ny, nstep});
            }
        }
        if (!found) cout << "Please give me another chance!\n";
    }
    return 0;
}

複雜度

時間 O(n × m × k)，空間 O(n × m × k)。k ≤ 10 保證效率。

關鍵點總結

1. 時間模作為狀態維度：將周期性障礙轉化為靜態圖層。
2. 三維訪問標記：同一位置不同時刻模視為不同狀態。
3. 石頭判邏輯：grid[nx][ny]=='#' && nmod!=0 時阻擋。
4. 起點時間為 0：0 % k == 0，石頭初始可通行。