文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

來源：acwing

分析：這題和普通的bfs求走迷宮問題很像，走迷宮告訴哪些點不能走，是永遠(yuǎn)不能走，這樣bfs的時候很容易處理。本題是這些障礙點在某段時間內(nèi)不能走，這就給初學(xué)者帶來了問題，這些變化的障礙點怎么處理呢？

其實，這里用到的技巧是拆點，這里的含義是多考慮一維，即時間。在a，b這段時間內(nèi)阻礙的話，就標(biāo)記為true，表示這段時間內(nèi)不能走。

while(T --){int x, y, a, b;cin >> x >> y >> a >> b;for(int i = a; i <= b; i ++)// 從a到b時刻不能走，標(biāo)記為trueg[x][y][i] = true;}

加上這樣的處理之后，就可以按照普通的bfs來搜了。

AC代碼

#include<bits/stdc++.h> using namespace std; const int N = 110, M = 310;int n, m, T; // g（x，y，z）表示點(x,y)在哪些時刻是障礙， //st表示該點走過或者不能走,都標(biāo)記為true bool g[N][N][M], st[N][N][M];// 結(jié)構(gòu)體表示點的坐標(biāo)，z表示時間 struct Node{int x, y, z; };int bfs(){queue<Node> q;st[1][1][0] = true;q.push({1, 1, 0});int dx[4] = { -1, 0, 1, 0}, dy[4] = { 0, 1, 0, -1};while(q.size()){auto t = q.front();q.pop();for(int i = 0; i< 4; i ++){int x = t.x + dx[i], y = t.y + dy[i],z = t.z + 1;if(x < 1 || x > n || y < 1 || y > m || g[x][y][z]) continue;if(!st[x][y][z]){if(x == n && y == m) return z; st[x][y][z] = true;q.push({x, y , z});}}}return -1; }int main(){cin >> n >> m >> T;while(T --){int x, y, a, b;cin >> x >> y >> a >> b;for(int i = a; i <= b; i ++)// 從a到b時刻不能走，標(biāo)記為trueg[x][y][i] = true;}cout << bfs() << endl; }

題目鏈接

https://www.acwing.com/problem/content/3233/

總結(jié)

以上是生活随笔為你收集整理的CSP认证201604-4游戏[C++题解]：bfs、拆点、迷宫问题加强版、三维数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。