关于”迷宫问题的一个疑问“
解答思路参考如下：
// 采用BFS找到通路即可。
// 假设有一个函数F，给定坐标 (i, j) 即可判断经过此坐标能否达目的地。
// 考虑一下几种情况：
// 最简单的情况：(i, j) 已经是目的地，我们返回 true 表示经过此坐标能到达目的地
// 基于坐标 (i, j) 可以往左走一步，调用函数F，将往左一步的坐标 (i - 1, j) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
// 基于坐标 (i, j) 可以往右走一步，调用函数F，将往右一步的坐标 (i + 1, j) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
// 基于坐标 (i, j) 可以往上走一步，调用函数F，将往上一步的坐标 (i, j - 1) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
// 基于坐标 (i, j) 可以往下走一步，调用函数F，将往下一步的坐标 (i, j + 1) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
// 而我们基于坐标 (i, j) 判断是否能分别往四个方向走一步，需要考虑 2 个方面的因素：
// 检查要去的坐标是否为墙壁，如果是墙壁肯定不能走
// 检查要去的坐标之前是否已经去过，好马不吃回头草，去过的坐标咱们也不走
// 最后我们只要将所有记录下来的坐标逆序输出就得到一条通路了。
#define true 1
#define false 0
#define maxsize 100
#include 1][y]==0){//右
// printf("(%d,%d)\n",x,y);
push(s,(x+1)*10+y);
path(N,M,num,flag,x+1,y,s); //
// pop(s,&x);
}
else if(num[x][y-1]==0&&y>0&&flag[x][y-1]==0){//上
// printf("(%d,%d)\n",x,y);
push(s,x*10+y-1);
path(N,M,num,flag,x,y-1,s);//
// pop(s,&x);
}
else if(num[x][y+1]==0&&y+11]==0){//下
// printf("(%d,%d)\n",x,y);
push(s,x*10+y+1);
path(N,M,num,flag,x,y+1,s);//
}
}//for
}
//1左2右3上4下
int main() {
int N=0,M=0;
scanf("%d",&N);
scanf("%d",&M);//ok
int num[N][M];
int flag[N][M];
for(int i=0;ifor(int j=0;jscanf("%d",&num[i][j]);
flag[i][j]=0;
}
}
stack s;
inisstack(&s);
path(N, M,num,flag,0,0,&s);
for(int i=0;i<=s.top;i++){
printf("(%d,%d)\n",s.date[i]/10,s.date[i]%10);
}
}
输入如下：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出如下：
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(2,1)
(2,2)
(2,3)
(2,4)
(1,4)
(0,4)
(0,3)
(0,2)
(3,4)
(4,4)
【重点】1.想知道为什么我的这个代码输出会直接往下走再往右走
2.然后栈的pop我不知道该放在哪里了，放到
push(s,x*10+y-1);
path(N,M,num,flag,x,y-1,s);
后面时，就把栈给删完了什么都不输出
已悬赏，求解答，谢谢！
重点是解决我这个上述问题而不是解决迷宫问题，迷宫问题参考其他视频已解决。
望采纳！！！点击回答右侧采纳即可！！！
1.你的代码中使用了一个for循环，在每次遍历到左、右、上、下四个方向时，都会进行一次递归调用。在递归调用的过程中，会继续遍历这四个方向，因此可能会出现先往下走再往右走的情况。
2.对于栈的pop操作，应该在每次递归调用后进行，例如在path函数的最后加上pop(s,&x);这样，在回溯到上一个节点时，就会将栈顶元素弹出。
另外，在你的代码中，每次递归调用path函数都会将当前点压入栈，但是在回溯到上一个节点时并没有将该点弹出栈中，这样会造成栈中元素过多，导致输出不正确。
还有一点，你的辅助栈是用来存储路径的，而不是存储当前搜索点的坐标。
1.在您的代码中，您使用了广搜算法(BFS)来解决迷宫问题。广搜算法每次会将当前节点的所有相邻节点全部加入队列，所以在您的代码中可能是先往下走再往右走。
2.pop操作应该在path函数走完一条路径后进行，例如在path函数的末尾加入pop操作。您可以在path函数返回之前加入pop操作，例如在下面这行之前加入pop操作：
return; 这样就不会把栈给删完了什么都不输出。
如果您把pop操作放在push操作之后，那么在path函数递归调用之前就会弹出栈顶元素，导致栈为空，无法输出路径。
除此之外，还可能有其他原因导致输出不正确，例如判断边界条件、判断是否走过该点等。您可以检查您的代码中是否有这些问题，并进行修改。
return;”应该在path函数的末尾，在path函数结束执行时加入这一行。 这是path函数结束时的标记，并且在这之前加上pop操作
例如：
void path(int N, int M, int num, int flag[][100], int x, int y, stack<int>&s) {
if(x == N && y == M) {
while(!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return;
}
if(x >= 1 && !flag[x - 1][y]) {
push(s, x*10 + y - 1);
flag[x - 1][y] = 1;
path(N, M, num, flag, x - 1, y, s);
flag[x - 1][y] = 0;
s.pop();
}
if(y >= 1 && !flag[x][y - 1]) {
push(s, x*10 + y - 1);
flag[x][y - 1] = 1;
path(N, M, num, flag, x, y - 1, s);
flag[x][y - 1] = 0;
s.pop();
}
if(x <= N && !flag[x + 1][y]) {
push(s, x*10 + y + 1);
flag[x + 1][y] = 1;
path(N, M, num, flag, x + 1, y, s);
flag[x + 1][y] = 0;
s.pop();
}
if(y <= M && !flag[x][y + 1]) {
push(s, x*10 + y + 1);
flag[x][y + 1] = 1;
path(N, M, num, flag, x, y + 1, s);
flag[x][y + 1] = 0;
s.pop();
}
}
1。输出直接往下走再往右走的原因是在 path 函数中，你按照顺序先检查了向下走，再检查向右走。在代码中，你使用了一个 for 循环来遍历上下左右四个方向，但是你把向下和向右的判断放在了循环体的最后，所以它会先检查到向下走，再检查到向右走。
如果你想让程序先检查向上和向左的路径，那么你需要把向上和向左的判断放在循环体的最前面。
建议你使用深度优先搜索算法来解决这个问题
另外，当起点和终点是障碍时，程序会引起死循环。你需要在path函数中增加特判.
2.正确的做法是在搜索完当前点的所有可能路径之后再将当前点弹出栈。
具体来说，在 path 函数中，当搜索完当前点的所有可能路径后，如果没有找到终点，那么就说明当前点是一个死点，需要回溯到上一个点继续搜索。因此应该在 path 函数的末尾加上一个 pop 操作，将当前点弹出栈。
for循环可以去掉，因为是依次搜索上下左右，如果某个方向不行就去掉了，不需要再次遍历，可以直接跳转到下一个方向。
更新代码如下：
void path(int N,int M,int num[N][M],int flag[N][M],int x,int y,stack *s){
int b=0;
flag[x][y]=1;//flag为1表示走过
if(x==N-1&&y==M-1){//是终点
return;
}
if(num[x-1][y]==0&&x>0&&flag[x-1][y]==0){//左
push(s,(x-1)*10+y);
path(N,M,num,flag,x-1,y,s);//
}
else if(num[x+1][y]==0&&x+1<N&&flag[x+1][y]==0){//右
push(s,(x+1)*10+y);
path(N,M,num,flag,x+1,y,s); //
}
else if(num[x][y-1]==0&&y>0&&flag[x][y-1]==0){//上
push(s,x*10+y-1);
path(N,M,num,flag,x,y-1,s);//
}
else if(num[x][y+1]==0&&y+1<M&&flag[x][y+1]==0){//下
push(s,x*10+y+1);
path(N,M,num,flag,x,y+1,s);
}
pop(s,&x);
}
这样就可以在搜索完当前点的所有可能路径之后，将当前点弹出栈，以便回溯到上一个点继续搜索。
注意：在回溯到上一个点之前，还需要将当前点的标记设置为未走过，否则下次遍历会认为这个点已经被走过了。
此外，在输出路径时，我们应该从栈顶开始，因为栈顶存储的是最后一个点，它是路径中最后一个点
问题1：为什么这个代码输出会直接往下走再往右走
这个代码中，在path()函数中有一个for循环，for循环内部有4个if语句分别检查当前格子的上下左右四个方向是否可以走，如果可以走，就调用path()函数继续往下走。
由于for循环在第一次运行时会检查左边的格子，如果左边的格子可以走，就会直接往左走。
后面的格子如果不能走，就会继续检查下一个方向的格子，如果可以走就往下走。
因此，如果第一次检查到的是左边的格子可以走，那么就会直接往左走，然后再往下走。
如果要改变这种走法，可以把for循环中的if语句的顺序改变，或者是改变判断的条件。
问题2：栈的pop我不知道该放在哪里了
pop操作应该放在path()函数的末尾，放在push和path调用之后。
这是因为在递归调用path()函数时，会先将当前格子的坐标压入栈中，然后再继续往下走。如果走到终点或者无路可走时，就应该回溯到上一个格子。因此pop操作应该在path()函数返回之前进行，这样才能保证栈中存储的是从起点到终点的路径。
请把pop操作放在path()函数末尾，在path()函数返回前执行，这样就能保证栈中存储的是从起点到终点的路径了。
可以在path()函数返回之后，在main函数中读出栈中存储的路径并输出。
void path(int N,int M,int num[N][M],int flag[N][M],int x,int y,stack *s){
flag[x][y]=1;//flag为1表示走过
if(x==N-1&&y==M-1){//是终点
push(s,(x)*10+y);
return;
}
else {
if(num[x-1][y]==0&&x>0&&flag[x-1][y]==0){//左
push(s,(x-1)*10+y);
path(N,M,num,flag,x-1,y,s);
}
else if(num[x+1][y]==0&&x+1<N&&flag[x+1][y]==0){//右
push(s,(x+1)*10+y);
path(N,M,num,flag,x+1,y,s);
}
else if(num[x][y-1]==0&&y>0&&flag[x][y-1]==0){//上
push(s,x*10+y-1);
path(N,M,num,flag,x,y-1,s);
}
else if(num[x][y+1]==0&&y+1<M&&flag[x][y+1]==0){//下
push(s,x*10+y+1);
path(N,M,num,flag,x,y+1,s);
}
}
if(x!=0||y!=0){
pop(s,&x);
}
}
我给你提供一下解决迷宫问题的思路吧，希望对你能有所启发：
递归求解、回溯求解和队列求解都可以进行破题。
1、递归求解
递归求解的基本思路是：
每个时刻总有一个当前位置，开始时这个位置是迷宫人口。
如果当前位置就是出口，问题已解决。
否则，如果从当前位置己无路可走，当前的探查失败，回退一步。
取一个可行相邻位置用同样方式探查，如果从那里可以找到通往出口的路径，那么从当前位置到出口的路径也就找到了。
在整个计算开始时，把迷宫的人口（序对）作为检查的当前位置，算法过程就是：
mark当前位置。
检查当前位置是否为出口，如果是则成功结束。
逐个检查当前位置的四邻是否可以通达出口（递归调用自身）。
如果对四邻的探索都失败，报告失败。
2、回溯求解
在回溯解法中，主要是用栈来存储可以探索的位置。利用栈后进先出的特点，在一条分路上探索失败时，回到最近一次存储的可探索位置。这是一种深度优先搜索的方法。
3、队列求解
队列求解算法中，以队列存储可以探索的位置。利用队列先进先出的特点，实现在每个分支上同时进行搜索路径，直到找到出口。这是一种广度优先搜索的方法。
但队列求解方法，不能直接得出找到的具体路径，要得到找到的路径还需要其他存储结构（如链表）。
问题如下，如下代码，修改的部分用====标出
然后方向的顺序调成的右-下-左-上，代码没有变
代码如下：
void path(int N,int M,int num[N][M],int flag[N][M],int x,int y,stack *s){
int b=0;
flag[x][y]=1;//flag为1表示走过
//for(int i=0;i<4;i++){ ====删除
if(x==N-1&&y==M-1){//是终点
// printf("(%d,%d)\n",x,y);
return;
}
//右 ==== 的时候是y+1，不是x+1，下面的方向类似错了，四个方向都要改
else if(num[x][y+1]==0&&y+1<M&&flag[x][y+1]==0){//右
// printf("(%d,%d)\n",x,y);
push(s,(x)*10+(y+1));
//pop(s, &x);
path(N,M,num,flag,x,y+1,s); //
//pop(s,&x);
}
else if(num[x+1][y]==0&&x+1<N&&flag[x+1][y]==0){//下
// printf("(%d,%d)\n",x,y);
push(s,(x+1)*10+y);
path(N,M,num,flag,x+1,y,s);//
}
else if(y>=1 && num[x][y-1]==0&&flag[x][y-1]==0){//左
// printf("(%d,%d)\n",x,y);
//push(s,(x-1)*10+y);
pop(s, &x);//====向左的时候pop
path(N,M,num,flag,x,y-1,s);//
}
else if(x >=1 && num[x-1][y]==0&&x>0&&flag[x-1][y]==0){//上
// printf("(%d,%d)\n",x,y);
//push(s,x*10+y-1);
pop(s, &x);//====向上的时候pop
path(N,M,num,flag,x-1,y,s);
}
//}====删除
}
首先，凭个人感觉，您这个应该是错误的dfs深搜算法，而不是bfs广搜算法
深搜算法采用的是一条路走到黑的方式，如果不通，则回溯，而广搜算法采用的是层先的搜索顺序，两者有本质上的区别
一般来说，深搜用递归（或栈）的方式，而广搜用队列的方式实现
这里您采用递归，所以他会一条路走到黑，不撞南墙不回头，然后您的for循环是没有意义的，你的if决定了他的搜索顺序
这里有一份标准的深搜代码，也可以找到最短路径，但不如广搜好，虽然是c++的，但是作者所用语法与c基本相同，没有用到c++特性，应该没有问题，头文件和命名空间忽略，供参考 , 您试试,两份代码(bfs + dfs)编写不易，望采纳
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int MAXNROAD = N * N;
const int Inf = 1e9;
int n,m;
int mp[N + 5][N + 5];
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0}; // 方向数组，模拟右、左、上、下
bool vis[N + 5][N + 5]; // 访问过的标记
int stk[MAXNROAD + 5][2],tp; // 为了方便理解，作者不使用STL，手动模拟
int min_ans = Inf,road[MAXNROAD + 5][2];// 最小步数，以及答案路径
void dfs(int x,int y,int step) { // 从x,y到n,m的路径已经走了step步
// 当前正在搜索的路径入栈
stk[++tp][0] = x;
stk[tp][1] = y;
if (step >= min_ans) { // 已经不是最优，剪枝，小小的优化
tp --; // 离开这个节点，出栈
return ;
}
if (x == n && y == m) {
min_ans = step; // 由于上面的判断，step 肯定 < min_ans
for(int i = 1;i <= tp;i ++) {
road[i][0] = stk[i][0]; // 拷贝路径
road[i][1] = stk[i][1];
}
tp --; // 离开这个节点，出栈
return ;
}
for(int i = 0;i < 4;i ++) { //循环使用在方向数组上
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && mp[nx][ny] == 0) { // 前四个判断顺序不能换，先判断是否越界，在判断是否可以通行
vis[nx][ny] = 1;
dfs(nx,ny,step + 1);
vis[nx][ny] = 0; // 递归求解最短路，是需要回溯的，这样才能保证最短，复杂度明显很劣
}
}
tp --; // 离开这个节点，出栈
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
scanf("%d",&mp[i][j]);
}
}
dfs(1,1,0);
// 步数比节点数少1
for(int i = 1;i <= min_ans + 1;i ++) {
printf("(%d,%d)\n",road[i][0],road[i][1]);
}
printf("共 %d 步\n",min_ans);
return 0;
}
这里还有一份bfs的模板，可以找到最短路径并输出，
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int MAXNROAD = N * N;
int n,m;
int mp[N + 5][N + 5];
int path[MAXNROAD][5],head,tail; // 为了方便您理解不使用STL,手动模拟队列
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0}; // 方向数组，模拟右、左、上、下
bool vis[N + 5][N + 5]; // 访问过的标记
int print_road(int id) {
int x = path[id][0];
int y = path[id][1];
int way = 1;
if (path[id][2] != 0) way += print_road(path[id][2]);
printf("(%d,%d)\n",x,y);
return way;
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
scanf("%d",&mp[i][j]);
}
}
head = tail = 1; // 队头，队尾
path[head][0] = 1; // 行
path[head][1] = 1; // 列
int endid = -1;
while(head <= tail) {
int x = path[head][0];
int y = path[head][1];
if (x == n && y == m) {
endid = head; // 记录最后一个结点的编号
break; // 此时队头就是答案
}
head ++; // 出队
for(int i = 0;i < 4;i ++) { // 循环使用在方向数组上的
int nx = x + dx[i];
int ny = y + dy[i]; // 计算新的坐标
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && mp[nx][ny] == 0) { // 前四个判断顺序不能换，先判断是否越界，在判断是否可以通行
vis[nx][ny] = 1;
path[++tail][0] = nx; // ++tail 是入队操作（队尾后移一位）
path[tail][1] = ny;
path[tail][2] = head - 1; // 记录是从哪里转移的
}
}
}
if (endid != -1) {
printf("共%d步",print_road(endid) - 1); // 因为先进队的先输出，但是只知道最后一个元素的下标，所以递归输出，步数比结点数少一
} else {
printf("No Way");
}
return 0;
}
这是关于迷宫问题的解答思路。迷宫问题是一种搜索问题，采用 BFS 找到通路是一种常用的做法。给定坐标 (i,j)，可以判断经过此坐标能否达到目的地。考虑几种情况：
如果坐标 (i,j) 已经是目的地，返回 true 表示经过此坐标能到达目的地。
如果坐标 (i,j) 可以往左走一步，调用函数 F，将往左一步的坐标 (i-1,j) 作为参数，如果 F 返回 true，表示此路为通路，将此坐标记录下来，然后返回 true。
如果坐标 (i,j) 可以往右走一步，调用函数 F，将往右一步的坐标 (i+1,j) 作为参数，如果 F 返回 true，表示此路为通路，将此坐标记录下来，然后返回 true。
如果坐标 (i,j) 可以往上走一步，调用函数 F，将往上一步的坐标 (i,j-1) 作为参数，如果 F 返回 true，表示此路为通路，将此坐标记录下来，然后返回 true。
如果坐标 (i,j) 可以往下走一步，调用函数 F，将往下一步的坐标 (i,j+1) 作为参数，如果 F 返回 true，表示此路为通路，将此坐标记录下来，然后返回 true。
在判断是否能往四个方向走一步时，需要考虑两个因素：
检查要去的坐标是否为墙壁，如果是墙壁肯定不能走。
检查要去的坐标之前是否已经去过，去过的坐标不能再次走，避免重复走重复路。
如果经过上述步骤，没有找到任何一条通路，就说明此迷宫无解，函数 F 返回 false。
这个解答思路的伪代码描述的很清楚，实际的实现中可能还需要一些细节的处理，例如记录路径、队列的实现等。此外，这个解答思路是基于二维迷宫，如果是三维或更高维的迷宫，需要进行相应的修改。
还有，这种解法是基于广度优先搜索BFS算法，如果想要使用其他算法，例如深度优先搜索DFS，就需要改变方向和队列的实现。
总之，这个思路是迷宫问题的一种解法，并不是唯一的解法，根据具体情况进行适当的修改和扩展就可以了。
--谷歌高级工程师