UVa1600 PatrolRobot 巡逻机器人(bfs)

题目大意：给定一个网络（1m,n20)m是row,n是col，求从（1，1）到点（m，n）的最短路径，其中0是空地，1是障碍物，给定k，表示不能连续穿过k个障碍物，

方法：bfs，其中必须要注意的是每个点的访问不能用二维数组储存，因为不同走法，每个点的累积穿过障碍物不同。假如第一次走过这个点，已经穿过了K个障碍物，下一次穿过这个点的时候可能就是累积穿过G个障碍物，所以这种情况要考虑在内。解决方法是设置三维数组，前2维存坐标，最后一维存累积穿过障碍物个数。

代码：

#include
#include 
#include 
#include 
using namespace std;
const int MAX = 20 + 5;
int mp[MAX][MAX]; int m, n, bar;
int vis[MAX][MAX][MAX];
int directx[4] = { 1,-1,0,0 };
int directy[4] = { 0,0,1,-1 };
bool isflag = false;
struct Node {int x, y;int step; int layer;Node() {}Node(int _x=1, int _y=1,int _step=0,int _layer=0) :x(_x), y(_y),step(_step),layer(_layer) {}
};
void bfs() {queue q;q.push(Node(1, 1,0,0));vis[1][1][0] = 1;while (!q.empty()) {Node  t = q.front(); q.pop();if (t.x == m && t.y == n) { isflag = true; cout << t.step<< endl; break; }for (int i = 0; i < 4; i++) {int x0 = t.x + directx[i];int y0 = t.y + directy[i];int layer = t.layer;if (mp[x0][y0]) {layer++;}else layer = 0;if (layer <=bar&&!vis[x0][y0][layer]&&x0>=1&&x0 <= m && y0 >= 1 && y0 <= n) {vis[x0][y0][layer] = 1;q.push(Node(x0, y0,t.step+1,layer));}}}
}
int main()
{int kase;cin >> kase;while (kase-- > 0) {isflag = false;memset(mp, 0, sizeof(mp));memset(vis, 0, sizeof(vis));cin >> m >> n;cin >> bar;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> mp[i][j];}}bfs();if (!isflag)cout << "-1" << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！