CSP认证201604-4游戏[C++题解]：bfs、拆点、迷宫问题加强版、三维数组

文章目录

• • • 题目解答
    • 题目链接

题目解答

来源：acwing

分析：这题和普通的bfs求走迷宫问题很像，走迷宫告诉哪些点不能走，是永远不能走，这样bfs的时候很容易处理。本题是这些障碍点在某段时间内不能走，这就给初学者带来了问题，这些变化的障碍点怎么处理呢？

其实，这里用到的技巧是拆点，这里的含义是多考虑一维，即时间。在a，b这段时间内阻碍的话，就标记为true，表示这段时间内不能走。

while(T --){int x, y, a, b;cin >> x >> y >> a >> b;for(int i = a; i <= b; i ++)// 从a到b时刻不能走，标记为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表示该点走过或者不能走,都标记为true bool g[N][N][M], st[N][N][M];// 结构体表示点的坐标，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时刻不能走，标记为trueg[x][y][i] = true;}cout << bfs() << endl; }

题目链接

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

总结

以上是生活随笔为你收集整理的CSP认证201604-4游戏[C++题解]：bfs、拆点、迷宫问题加强版、三维数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。