深度优先搜索（DFS)解决迷宫问题

例题

	定义一个二维数组：

	int maze[5][5] = {

						0, 1, 0, 0, 0,

						0, 1, 0, 1, 0,

						0, 0, 0, 0, 0,

						0, 1, 1, 1, 0,

						0, 0, 0, 1, 0,

					   };

 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

#include<stdio.h>

int a[10][10];//迷宫函数 
int v[10][10];//标记函数，用来标记已经走过的格子，走过为1，没走过为0

int tx[10],ty[10];//储存当前路径 
int minx[10],miny[10];//储存最小路径 

int dx[4]={0,1,0,-1};//方向函数,规定方向为顺时针访问 
int dy[4]={1,0,-1,0};
 
 int min=9999;//定义最小步数
 
void dfs(int x,int y,int step)//DFS函数
{
	int i;
	tx[step]=x;ty[step]=y; 
	
	if(x==4&&y==4)//如果已经走到终点 
	{
		if(step<min)//如果当前步数小于最小步数，更新最小值，并更新最短路径	
		{
				min=step;
				//更新最短路径
				for(i=0;i<=step;i++)
				{
					minx[i]=tx[i];
					miny[i]=ty[i];
				} 
		}
		return;	
	}
	
	//顺时针搜索 
	for(i=0;i<4;i++)
	{
		int tx,ty;
		tx=x+dx[i];//下一步的坐标 
		ty=y+dy[i];
		if(a[tx][ty]==0&&v[tx][ty]==0&&tx>=0&&tx<=4&&ty>=0&&ty<=4)//可以走且没有被访问 
		{
			v[tx][ty]=1;//设置为已经访问 
			dfs(tx,ty,step+1);//进行下次DFS，步数+1 
			v[tx][ty]=0;//将访问过的还原为未访问 
		} 	
	}	
} 
int main()
{
	int i,j;
	for(i=0;i<5;i++)
		for(j=0;j<5;j++)
			scanf("%d",&a[i][j]);
	v[0][0]=1;//起始坐标已经访问
	dfs(0,0,0);//起始步数为0
	for(i=0;i<=min;i++)
		printf("(%d, %d)\n",minx[i],miny[i]);
	return 0;					
}