问题描述

关于使用回溯法求解迷宫问题

#include
using namespace std ;
const int m = 4 , p = 4 ;
struct offsets {
int a , b ;
char *dir ;
};
offsets move[8] ;
int Maze[m+2][p+2] ;
int mark[m+2][p+2] ;
int main (){
int i , j;
int SeekPath (int x ,int y ) ;
offsets move[8] = {{-1,0,"N"},{-1,1,"NE"},{0,1,"E"},{1,1,"SE"},{1,0,"S"},{1,-1,"SW"},{0,-1,"W"},{-1,-1,"NW"}} ;
for(i = 0 ;i< m+2 ;i++) {
for(j=0;j

cin >> Maze[i][j] ;
}
}
for(i = 0 ;i < m+2 ;i++) {
for(j = 0;j<p+2 ;j++) {
mark[i][j] = 0 ;
}
}
mark[1][1] = 1 ;
if(SeekPath(1,1)) {
cout << "(" << 1 << "," << 1 << ") ," << "dir" << "E" <<endl;
}
}

int SeekPath (int x ,int y ) {
int i ,g ,h ;
char *d;
if(x == m && y == p) return 1 ;
for(i = 0 ;i < 8 ;i++) {
g = x+ move[i].a ;
h = y+ move[i].b ;
d = move[i].dir ;
if(Maze[g][h] == 0 && mark[g][h] == 0) {
mark[g][h] = 1 ;
if (SeekPath (g,h)) {
cout << "(" << g <<"," << h <<")," << "dir" <<" ," ;
return 1 ;
}
}
}
if(x == 1 && y== 1 ) cout << "no path in Maze " <<endl ;
return 0 ;

}

不知道为何输入地图进去后总是显示 "no path in Maze"
两天了实在找不到问题在哪，希望能有大神帮忙指点

解决方案

来个大神啊 = = 实在不知道哪里出问题了，改了好几遍了

解决方案二：

注释不够详细，不过粗略看一下，按照递归来说，递归前后状态应该得一致。

 mark[g][h] = 1 ;
if (SeekPath (g,h)) {
cout << "(" << g <<"," << h <<")," << "dir" <<" ," ;
return 1 ;
}

想这段代码，一段返回0，那mark[g][h]状态就一直是1，后续及时递归回去，这个节点的状态就不会变。