鱼C论坛

 找回密码
 立即注册
查看: 3561|回复: 4

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

[复制链接]
发表于 2013-11-2 11:01:59 | 显示全部楼层 |阅读模式
3鱼币
(代码见附件)visit函数的最后maze[i][j]=0不懂,请帮忙解释下哈

老鼠走迷宫.rar

583 Bytes, 下载次数: 34

最佳答案

查看完整内容

首先,满足第一个if语句if(i==endI&&j==endJ),表示此事maze[j]为出口。因此暂不看。 然后,maze[j]=1;maze[j]=0;这两句都是改变数组的地方,第一个表示将当前位置改为显示路径。而第二则是将当前位置改回为普通道路。 关键递归地方是那四个if if(maze[j+1]==0) visit(i,j+1); if(maze[j]==0) visit(i+1,j); if(maze[j-1]==0) visit(i,j-1); if(maze[j]==0) visit(i-1,j); 如果上下左右存在通路则进入递归。而最后一个maz ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2013-11-2 11:02:00 | 显示全部楼层
本帖最后由 musilintan 于 2013-11-4 20:05 编辑

首先,满足第一个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]

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2013-11-2 11:24:09 | 显示全部楼层
类似二叉树查找问题,会用到递归吧,
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2013-11-2 14:57:44 | 显示全部楼层
把问题代码贴出来比较好看,好要下代码。。。好麻烦。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2013-11-3 17:57:35 | 显示全部楼层
本帖最后由 笑着前进 于 2013-11-3 17:59 编辑
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]
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 01:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表