老鼠走迷宫输出全部路线的算法问题

笑着前进

（代码见附件）visit函数的最后maze[i][j]=0不懂，请帮忙解释下哈

musilintan

笑着前进 发表于 2013-11-3 17:57

                               
登录/注册后可看大图

#include"stdio.h"
#include"stdlib.h"
#include"iostream"

首先，满足第一个if语句if(i==endI&&j==endJ)，表示此事maze[i][j]为出口。因此暂不看。
然后，maze[i][j]=1;maze[j]=0;这两句都是改变数组的地方，第一个表示将当前位置改为显示路径。而第二则是将当前位置改回为普通道路。
关键递归地方是那四个if[/i][/i]
[i][i][i]if(maze[i][j+1]==0) visit(i,j+1);
if(maze[i+1][j]==0) visit(i+1,j);
if(maze[i][j-1]==0) visit(i,j-1);
if(maze[i-1][j]==0) visit(i-1,j);
如果上下左右存在通路则进入递归。而最后一个maze[j]=0;也就是当进入死胡同的时候将当前位置的1还原为0（普通道路）例如这种情况：
2 2 2
2 1 1
2 2 2
此时就进入死胡同然后一层一层的退出去，将误当做正确路径道路全部还原为0.
最后，终将会有一个递归i和j刚好为出口，然后进入if语句显示路径。[/i][/i][/i][/i][/i]

cainiao367

类似二叉树查找问题，会用到递归吧，

musilintan

把问题代码贴出来比较好看，好要下代码。。。好麻烦。。。

笑着前进

musilintan 发表于 2013-11-2 14:57

                               
登录/注册后可看大图

把问题代码贴出来比较好看，好要下代码。。。好麻烦。。。

#include"stdio.h"
#include"stdlib.h"
#include"iostream"
int maze[9][9]=
        {
         {2,2,2,2,2,2,2,2,2},
         {2,0,0,0,0,0,0,0,2},
         {2,0,2,2,0,2,2,0,2},
         {2,0,2,0,0,2,0,0,2},
         {2,0,2,0,2,0,2,0,2},
         {2,0,0,0,0,0,2,0,2},
         {2,2,0,2,2,0,2,2,2},
         {2,0,0,0,0,0,0,0,2},
         {2,2,2,2,2,2,2,2,2}
        };
int startI=1,startJ=1;/*入口*/
int endI=7,endJ=7;/*出口*/
int success=0;
void visit(int i,int j);
int main()
{
        int i,j;
        printf("显示迷宫\n");
        for(i=0;i<9;i++)
        {
                for(j=0;j<9;j++)
                {
                        if(maze[i][j]==2)
                        {
                                printf("|");
                        }
                        else
                        {
                                printf(" ");
                        }
                }
                printf("\n");
        }
        system("pause");
        visit(startI,startJ);

    system("pause");
        return 0;
}
void visit(int i,int j)
{
        int m,n;
        maze[i][j]=1;
        if(i==endI&&j==endJ)
        {
                printf("\n显示路径:\n");
                        for(m=0;m<9;m++)
                        {
                                for(n=0;n<9;n++)
                                {
                                        if(maze[m][n]==2)
                                        {
                                                printf("|");
                                        }
                                        else if(maze[m][n]==1)
                                                printf("@");
                                        else
                                                printf(" ");
                                }printf("\n");
                        }
        }
               
        if(maze[i][j+1]==0) visit(i,j+1);
        if(maze[i+1][j]==0) visit(i+1,j);
    if(maze[i][j-1]==0) visit(i,j-1);
    if(maze[i-1][j]==0) visit(i-1,j);
        maze[i][j]=0;
}[/i][/i][/i][/i][/i]