我们需要做的事情：从(1,1)走到(m,n)
把这个问题进行分解
可以看成，①从(1,1)往八个方向走一步②再从这个点走到(m,n),我们发现，②也是在重复从(1,1)走到(m,n)的过程，直到我们走到(m,n)的位置，然后结束这个过程，告诉前面的点找到(m,n)了（return 1）。因此我们可以使用递归函数，假设函数名是solve(int x,int y)，表示从(x,y)走到(m,n)，那么我们的函数就可以写成
int solve(int x,int y){
if(x==m&&y==n){
return 1;
}
if(puzzle[x-1][y-1]==0){//左上
if(solve(x-1,y-1)){
return 1;
}
}
if(puzzle[x][y-1]==0){//上方
if(solve(x,y-1)){
return 1;
}
}
if(puzzle[x+1][y-1]==0){//右上
if(solve(x+1,y-1)){
return 1;
}
}
if(puzzle[x+1][y]==0){//右
if(solve(x+1,y)){
return 1;
}
}
if(puzzle[x+1][y+1]==0){//右下
if(solve(x+1,y+1)){
return 1;
}
}
if(puzzle[x][y+1]==0){//下
if(solve(x,y+1)){
return 1;
}
}
if(puzzle[x-1][y+1]==0){//左下
if(solve(x-1,y+1)){
return 1;
}
}
if(puzzle[x-1][y]==0){//左边
if(solve(x-1,y)){
return 1;
}
}
return 0;//如果八个方向都没有找到，说明这个点到不了(m,n)
}
然而如果我们使用这个函数，我们会发现它陷入了死循环，因为假设我们从(1,1)递归执行solve(2,2)，在执行solve(2,2)的过程中，我们又会走到(1,1)，然后一直重复在(1,1)和(2,2)之间来回走的过程，陷入死循环，因此，我们需要进行限制，让已经走过的路不再纳入考虑范围里，于是我们可以使用一个visit数组，来表示在这个过程中这个点有没有走过，如果八个方向都不能走，函数会到末尾结束，返回上一个点，相当于后退了一步，所以我们需要把visit标记清除
int solve(int x,int y){
visit[x][y]=1;//标记这个点，表示这个点我们已经走过了，之后走的时候不走它
if(x==m&&y==n){
return 1;
}
if(puzzle[x-1][y-1]==0&&visit[x-1][y-1]==0){//左上，检验可不可以走的时候同时检验这个点有没有走过
if(solve(x-1,y-1)){
return 1;
}
}
if(puzzle[x][y-1]==0&&visit[x][y-1]==0){//上方
if(solve(x,y-1)){
return 1;
}
}
if(puzzle[x+1][y-1]==0&&visit[x+1][y-1]==0){//右上
if(solve(x+1,y-1)){
return 1;
}
}
if(puzzle[x+1][y]==0&&visit[x+1][y]==0){//右
if(solve(x+1,y)){
return 1;
}
}
if(puzzle[x+1][y+1]==0&&visit[x+1][y+1]==0){//右下
if(solve(x+1,y+1)){
return 1;
}
}
if(puzzle[x][y+1]==0&&visit[x][y+1]==0){//下
if(solve(x,y+1)){
return 1;
}
}
if(puzzle[x-1][y+1]==0&&visit[x-1][y+1]==0){//左下
if(solve(x+1,y+1)){
return 1;
}
}
if(puzzle[x-1][y]==0&&visit[x-1][y]==0){//左边
if(solve(x-1,y)){
return 1;
}
}
visit[x][y]=0;//八个点都走不过去，我们退回到上一个点，在这之前，因为我们是往后退了，所以这个点重新标记成我们没有来过
return 0;//如果八个方向都没有找到，说明这个点到不了(m,n)
}
找路的部分已经写好了，那么我们如何把路径输出呢，我们想到，我们找到(m,n)的时候，return 了 1，之后回到(m,n)的前一个点，在
if(solve(x+1,y)){
return 1;
}
这个语句中又向上一个点返回了1，也就是按照原路一直return 1，所以我们可以在return 1之前加一个输出，输出这个时候的(x,y)，就可以把路径输出
int solve(int x,int y){
visit[x][y]=1;//标记这个点，表示这个点我们已经走过了，之后走的时候不走它
if(x==m&&y==n){
printf("(%d,%d)\n",x,y);
return 1;
}
if(puzzle[x-1][y-1]==0&&visit[x-1][y-1]==0){//左上，检验可不可以走的时候同时检验这个点有没有走过
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x][y-1]==0&&visit[x][y-1]==0){//上方
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x+1][y-1]==0&&visit[x+1][y-1]==0){//右上
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x+1][y]==0&&visit[x+1][y]==0){//右
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x+1][y+1]==0&&visit[x+1][y+1]==0){//右下
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x][y+1]==0&&visit[x][y+1]==0){//下
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x-1][y+1]==0&&visit[x-1][y+1]==0){//左下
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
if(puzzle[x-1][y]==0&&visit[x-1][y]==0){//左边
if(solve(x+1,y)){
printf("(%d,%d)\n",x,y);
return 1;
}
}
visit[x][y]=0;//八个点都走不过去，我们退回到上一个点，在这之前，因为我们是往后退了，所以这个点重新标记成我们没有来过
return 0;//如果八个方向都没有找到，说明这个点到不了(m,n)
}
评论 (1)