发信人: TonyZhang (四处走走), 信区: Npsos
标  题: 自己琢磨的迷宫新解法
发信站: BBS 哈工大紫丁香站 (Mon Oct 11 19:38:01 2004)

p.s. 自己琢磨出来的，还不只到以前有没有人想出来过，如有巧合纯属偶然

基本的想法：算出每一个点（迷宫的一个格子）四周的墙壁面数，如果是死路则数值为0或
 
1 
，下一步就是把这个死路点标记为墙壁。重复这个过程，直到没有更新。那么剩下的路径
 
就是所有的路径重合后的图。 

基本代码如下： 
//全局数据 
char maze[50][51]={0}; 
int  num[50][51]; 
int isFinished=0; 
int input=0; 

//使用说明
void usage(){ 
    printf("A new method of maze problem\n"); 
    printf("Now enter the map with a square map\n"); 
    printf("x for wall & space for path please\n\n"); 
} 

//打印迷宫 
void printMaze(){ 
        int m,n; 
        for(m=0;m<50;m++) 
        for(n=0;n<51;n++) 
            if(maze[m][n]!='0') 
                printf("%c",maze[m][n]); 
} 
//计算每一个点的四周墙壁数并返回 
int countEach(int x,int y){ 
        int result=0,i; 
        char mark[4]; 
        mark[0]=maze[x][y-1]; 
        mark[1]=maze[x][y+1]; 
        mark[2]=maze[x-1][y]; 
        mark[3]=maze[x+1][y]; 

        for(i=0;i<4;i++) 
           if(mark[i]=='x') result++; 

        return result; 
} 
//将迷宫每一个点的数据一一对应得记入一个二维数组 
void record(){ 
    int m,n; 
    for(m=1;m<input;m++) 
        for(n=1;n<input+1;n++) 
            num[m][n]=countEach(m,n); 
} 
//分析过程 
void parse(){ 
        int m,n; 
        isFinished=1; 

        for(m=0;m<input;m++) 
            for(n=0;n<input+1;n++) 
                if(num[m][n]==1 || num[m][n]==0){ 
                    maze[m][n]='x'; 
                    isFinished=0; 
                } 
        record(); 
        printMaze(); 
} 

//主函数 
main(){ 
    int i,m,n,p; 
     
    //初始化 
    for(m=0;m<50;m++) 
        for(n=0;n<51;n++){ 
            maze[m][n]='0'; 
            num[m][n]=-1; 
        } 

    usage(); 
     
    //读入迷宫 
    printf("Enter the width of the square:(<50):"); 
    scanf("%d",&input); 
    for(i=0;i<input;i++){ 
          scanf("%s",maze[i]); 
    } 
    for(i=0;i<input;i++){ 
         maze[i][input]='\n'; 
    } 

    //初始化原始迷宫的数据 
    printf("input is %d:\n",input); 
    printf("\nThis is the original maze you entered\n"); 
    printMaze(); 
    record(); 
     
    //分析 
    while(isFinished==1) 
        parse(); 
        
    getch(); 
} 

p.s. 编译通过但执行时还有点问题，还请各位大虾改正。 


--
学的是技术，而不是java或.net,要看清本质

※ 修改:·TonyZhang 於 Oct 11 19:39:33 2004 修改本文·[FROM: 210.46.79.149]
※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 210.46.79.149]