[C++知识库]C语言处理迷宫问题（如何用一个函数来寻找路径）

迷宫问题

问题描述：在一组m行n列的数据中’1’表示墙，'0’表示路；左上角第二行第二列为起点，同理右下角第二行第二列为为终点。你需要编写一个代码来寻找路径。

分析问题

首先对于这个问题，我们需要1.获取迷宫；2.寻找路径；3.打印路径；
其中获取迷宫和打印路径比较简单，本文不作详细分析，因个人技术有限此部分代码较为繁琐，仅供参考。其他代码只要能读入迷宫数据即可。

#include<stdio.h>
char a[1007][1007]={0},b[1007]={0};//定义二维数组存放迷宫，一维数组辅助导入迷宫 
int bate=1;//标志，如果找到bate=0 
int m=0,n=0;//定义行、列 

void get(){//获取迷宫
	char s[20];//用来存放文件名 
    printf("请输入文件名：");
    scanf("%s",&s);
FILE *fp;
    int i,j;
	int ch;
    if((fp=fopen(s,"r"))==NULL)
		printf("错误\n"); 
    else{
    	while(fgets(s,1007,fp)!=NULL)m++;    //读行数
		rewind(fp);//回文件起始位置
		fscanf(fp,"%s",b);  
	while(b[n])n++;    //计算列 
		rewind(fp);//回文件起始位置
		for(i=0;i<m;i++){//将迷宫读入数组a中 
		fscanf(fp,"%s",b);
	    	j=0;
    	while(b[j]){
			a[i][j]=b[j];
			j++;
	   	};
    	}
	printf("获取成功！\n");//提示 
	} 
fclose(fp);//关闭文件 
}

寻找路径

怎么走迷宫呢？大家可能会想到一直走，遇到分岔路就右转（左转），走不通就退回到上一个分岔路继续。对于程序而言，也可以用同样的方法，既然如此需要注意的就有:
1.向哪里走
2.接下来向哪里走
3.走不通怎么退回去
4.我又走回来了怎么办
5.如何知道密宫有没有出口
…
由此可见，当我在写find()方法时需要当前位置的坐标，这样才能随时知道自己是否到达终点，或者走到死路中。同时如果我想解决接下来向哪里走的问题，那我必须引入一个变量表示方向。那这样一个方法就可以解决前两个问题。
对于第三个问题，如果要退回去再写一个方法其实没有必要，我们完全可以将上述方法进行递归调用（为什么递归？因为每次寻找路径状态都相似）我们可以让程序按一定顺序寻找路径。（例如先向右，走不通就向下）
如果担心我又走回来了怎么办，很简单，可以在走过的路径做上标记，在判断时当作’墙’。
如何知道密宫有没有出口，当程序所有情况都考虑了，遍历结束后仍没有答案，那么就是没有出口。
以下为方法代码

int find(int x,int y,int z){//z=0/1/2/3,表示方向右/向下/向左/向上 
	if(x+y==m+n-4)bate=0;//判断是否出口 
	//如果z=3，说明从下往上走，那么下一步不考虑向下；后续同理 
	if(bate&&z!=3&&a[x+1][y]=='0'){//下
	    printf("-(%d,%d)下",x,y);
		a[x][y]='*';//记录路径
	    find(x+1,y,1);
    }
	if(bate&&z!=2&&a[x][y+1]=='0'){//右
		printf("-(%d,%d)右",x,y);
		a[x][y]='*'; 
	    find(x,y+1,0);
    }
	if(bate&&z!=0&&a[x][y-1]=='0'){//左
		printf("-(%d,%d)左",x,y);
		a[x][y]='*';
		find(x,y-1,2);
	}
	if(bate&&z!=1&&a[x-1][y]=='0'){//上
	    printf("-(%d,%d)上",x,y);
		a[x][y]='*';
		find(x-1,y,3);
	}
	if(bate){//后退 
	    a[x][y]='0';//撤销路径 
	    printf("-(%d,%d)退",x,y);
	}  
	return 0;
}

1-在代码中x,y（行，列）表示了当前位置；z表示方向（来者方向）：
A->(向右)->B->(向下)->C若当前位置为B，Z表示向右。

2-第一个if语句中判断当前位置是否为密宫出口，bate作为标记；
3-第二个if语句（bate等于1，目前还未找到出口）（z！=3）
从上一个位置到这里方向=3（向上），那么我就不需要找向下的路（不走回头路）每走完一步将当前位置标为’’;
4-四个方向都遍历结束后进行最后判断（每个方向都会遍历，所以不用考虑上下左右还是上右下左等问题，现实中是为了方便人去记忆才一直向右或左），此时是否找到路径如果没有（bate等于1）执行操作将当前位置的’‘变更为’0’;返回到上一级。
5-最后附上剩余代码

void out(int m,int n){//输出迷宫a 
	int i,j;
	printf("\n");
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
		printf("%c",a[i][j]);
		}
	printf("\n");
	}
}

int main(){
    get();//获取迷宫
        printf("行=%d,列=%d\n",m,n);//输出行列 
    out(m,n);//输出迷宫 
        find(1,1,0);//寻找---0表示向右；1，1表示下一步位置 
    if(!bate){//补充入口、出口 
    	a[1][0]='s';a[m-2][n-2]='*';a[m-2][n-1]='e';
	}
	if(bate){
		printf("没有通路\n");
	}
    out(m,n);//输出迷宫
return 0; 
}

文章中的代码均按顺序排列
以下为样例一（请以文本文档保存后输入文件名即可使用）

111111111111111111111111111111
101000100011111111111110001111
100010001011111111111111011111
111111110011111111111111011111
111000000111111111100001111111
100011111111111111100011111111
101110000000111110000111111111
101000111110111111111100001111
101011111110111111110000111111
100011111110111111110001111111
111111111110000000001100111111
111111111111111111100000000001
111111111111111111111111111111
样例二
111111111111111
100011111111111
111011111111111
100000010000001
100000010000001
100110010011001
100110000011001
100110010011001
100000010000001
100000010000001
111111111101111
111111111101111
100000011101111
100000011001111
100110000001111
100110011111111
100110011111111
100000010000001
100000010000001
111101110011001
111101110011001
111101110011001
111101110000001
111101110000001
111101111011011
111100110011011
111100000011011
111111111111001
111111111111001
111111111111111