題目大意：給定一個(gè)網(wǎng)絡(luò)（1m,n20)m是row,n是col，求從（1，1）到點(diǎn)（m，n）的最短路徑，其中0是空地，1是障礙物，給定k，表示不能連續(xù)穿過(guò)k個(gè)障礙物，

方法：bfs，其中必須要注意的是每個(gè)點(diǎn)的訪問(wèn)不能用二維數(shù)組儲(chǔ)存，因?yàn)椴煌叻?#xff0c;每個(gè)點(diǎn)的累積穿過(guò)障礙物不同。假如第一次走過(guò)這個(gè)點(diǎn)，已經(jīng)穿過(guò)了K個(gè)障礙物，下一次穿過(guò)這個(gè)點(diǎn)的時(shí)候可能就是累積穿過(guò)G個(gè)障礙物，所以這種情況要考慮在內(nèi)。解決方法是設(shè)置三維數(shù)組，前2維存坐標(biāo)，最后一維存累積穿過(guò)障礙物個(gè)數(shù)。

代碼：

#include<iostream> #include <string> #include <string.h> #include <queue> 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<Node> 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; }

?

總結(jié)

以上是生活随笔為你收集整理的UVa1600 PatrolRobot 巡逻机器人(bfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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