迷宫问题 bfs _问题

【迷宫问题 bfs】大道之行，天下为公。这篇文章主要讲述迷宫问题 bfs相关的知识，希望能为你提供帮助。
题目链接：迷宫问题
天啦撸。最近怎么了。小bug缠身，大bug 不断。然这是我大腿第一次给我dbug。虽然最后的结果是。我............bfs入队列的是now..............
然后。保存路径的一种用的string 。一种用的数组。大同小异。根据就是我bfs 先搜到的绝壁就是步数最少的、
附代码：
pre 数组

文章图片

1 5 6 #include7 #include < string.h> 8 #include 9 #include 10 #include < string> 11 using namespace std; 1213 struct Node { 14int x, y; 15 }now, temp, ans; 1617 int mp[10][10]; 18 int vis[10][10]; 19 Node que[210]; 20 Node pre[210]; 2122 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; 2324 bool check(Node a) { 25if (a.x > = 0 & & a.x < 5 & & a.y > = 0 & & a.y < 5 & & !vis[a.x][a.y] & & mp[a.x][a.y] == 0) 26return true; 27return false; 28 } 2930 int head = 0, tail = 0; 3132 void bfs() { 33while(head < tail) { 34now = que[head++]; 35if (now.x == 4 & & now.y == 4) { 36return; 37} 38for (int i=0; i< 4; ++i) { 39temp.x = now.x + dir[i][0]; 40temp.y = now.y + dir[i][1]; 4142if (check(temp)) { 43que[tail++] = temp; 44vis[temp.x][temp.y] = 1; 45int id = temp.x * 5 + temp.y; 46pre[id].x = now.x, pre[id].y = now.y; 47} 48} 49} 50 } 5152 void outPre(int num) { 53if (pre[num].x == -1 & & pre[num].y == -1) 54return; 55else outPre(5*pre[num].x+pre[num].y); 56cout < < " (" < < pre[num].x < < " , " < < pre[num].y < < " )\\n" ; 57 } 5859 int main() { 60head = 0, tail = 0; 61memset(vis, 0, sizeof(vis)); 6263for (int i=0; i< 5; ++i) { 64for (int j=0; j< 5; ++j) { 65cin > > mp[i][j]; 66} 67} 68now.x = 0, now.y = 0; 69vis[0][0] = 1; 70que[tail++] = now; 71pre[0].x = -1, pre[0].y = -1; 72bfs(); 7374outPre(24); 75cout < < " (4, 4)\\n" ; 76return 0; 77 }

View Codestring

文章图片

1 5 6 #include7 #include < string.h> 8 #include 9 #include 10 #include < string> 11 using namespace std; 1213 struct Node { 14int x, y; 15string ansStep; 16 }now, temp, ans; 1718 int mp[10][10]; 19 int vis[10][10]; 20 Node que[210]; 2122 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; 23 bool check(Node a) { 24if (a.x > = 0 & & a.x < 5 & & a.y > = 0 & & a.y < 5 & & !vis[a.x][a.y] & & mp[a.x][a.y] == 0) 25return true; 26return false; 27 } 2829 int head = 0, tail = 0; 3031 void bfs() { 32while(head < tail) { 33now = que[head++]; 34if (now.x == 4 & & now.y == 4) { 35now.ansStep += ‘ \\0‘ ; 36ans.ansStep = now.ansStep; 37return; 38} 39for (int i=0; i< 4; ++i) { 40temp.x = now.x + dir[i][0]; 41temp.y = now.y + dir[i][1]; 4243if (check(temp)) { 44vis[temp.x][temp.y] = 1; 45temp.ansStep = now.ansStep; 46temp.ansStep += temp.x + ‘ 0‘ ; 47temp.ansStep += temp.y + ‘ 0‘ ; 48que[tail++] = temp; 49} 50} 51} 52 } 5354 int main() { 55head = 0, tail = 0; 56memset(vis, 0, sizeof(vis)); 5758for (int i=0; i< 5; ++i) { 59for (int j=0; j< 5; ++j) { 60cin > > mp[i][j]; 61} 62} 63now.x = 0, now.y = 0; 64now.ansStep += " 00" ; 6566vis[0][0] = 1; 67que[tail++] = now; 68bfs(); 6970string ansstr = ans.ansStep; 71int len = ansstr.length(); 72for (int i=0; i2

View Code