DFS深搜寻找迷宫最短路径

 （左：迷宫    右： 最短路径）

 代码：

#include
#include
#include
#define N 1001
using namespace std;

struct St
{
	int x;
	int y;
}s[N],sMin[N];//记录路径坐标的栈

int Map[25][25] = {
	//迷宫地图
	   {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	   {1,1,1,3,3,3,3,3,1,1,1,1,1,3,3,3,3,3,1,1,1},
	   {1,1,3,1,1,1,1,1,3,1,1,1,3,1,1,1,1,1,3,1,1},
	   {1,3,1,1,0,0,0,1,1,3,1,3,1,1,0,0,0,1,1,3,1},
	   {3,1,1,0,1,1,1,0,1,1,3,1,1,0,1,1,1,0,1,1,3},
	   {3,1,0,1,1,0,1,1,0,1,9,1,0,1,1,0,1,1,0,1,3},
	   {3,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,3},
	   {3,1,0,1,1,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,3},
	   {3,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,3},
	   {1,3,1,1,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,3,1},
	   {1,1,3,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,3,1,1},
	   {1,1,1,3,1,0,1,0,1,0,1,0,1,0,1,0,1,3,1,1,1},
	   {1,1,1,1,3,1,0,1,1,0,1,0,1,1,0,1,3,1,1,1,1},
	   {1,1,1,1,1,3,1,0,1,0,1,0,1,0,1,3,1,1,1,1,1},
	   {1,1,1,1,1,1,3,1,1,0,1,0,1,1,3,1,1,1,1,1,1},
	   {1,1,1,1,1,1,1,3,1,1,0,1,1,3,1,1,1,1,1,1,1},
	   {1,1,1,1,1,1,1,1,3,1,1,1,3,1,1,1,1,1,1,1,1},
	   {1,1,1,1,1,1,1,1,1,3,4,3,1,1,1,1,1,1,1,1,1},
	   {1,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,1,1},
	   {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
	   {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}
};
int stepMap[N][N];//路径地图
int flag[N][N];//标记地图
int dx[4] = {1, 0, -1, 0};//方向数组
int dy[4] = {0, 1, 0, -1};//上右左下
int k = 1;//n:行列数
int stepMin = N;
int Beginx, Beginy, Endx, Endy;
int bound = 21;

void oldMap()
{
	for (int i = 0; i < bound; i++)
	{
		for (int j = 0; j < bound; j++)
		{
			cout << Map[i][j] << ' ';
		}
		cout << endl;
	}	
}

void findAim()
{
	for (int i = 0; i < bound; i++)
	{
		for (int j = 0; j < bound; j++)
		{
			if (Map[i][j] == 9)
			{
				Beginx = i;
				Beginy = j;
				Map[Beginx][Beginy] == 1;
			}
			if (Map[i][j] == 4)
			{
				Endx = i;
				Endy = j;
				Map[Endx][Endy] == 1;
			}
		}
	}
}

void Min()
{
	memset(sMin, 0, sizeof(sMin));//结构体数组初始化用来存储最短路径
	for (int i = 0; i < stepMin; i++)
	{
		sMin[i] = s[i];//将坐标栈的坐标存入sMin数组中
	}
}

void Output()
{
	for (int i = 0; i < stepMin; i++)
	{
		int x = sMin[i].x;
		int y = sMin[i].y;
		stepMap[x][y] = 1;//将最短路径标记在路径地图中
	}
	for (int i = 0; i < bound; i++)//输出地图
	{
		for (int j = 0; j < bound; j++)
		{
			cout << stepMap[i][j] << ' ';
		}
		cout << endl;
	}
}

void DSF(int x, int y,int step)
{
	if (x == Endx - 1 && y == Endy - 1)
	{//到达终点输出
		if (step < stepMin)
		{
			stepMin = step;
			Min();
		}
		return;
	}

	int tx, ty;
	for (int i = 0; i < 4; i++)
	{
		tx = x + dx[i];
		ty = y + dy[i];
		if (tx <= bound && ty <= bound)//判断是否越界
		{
			if (flag[tx][ty] == 0 && Map[tx][ty] == 1)
			{
				flag[tx][ty] = 1;
				s[k].x = tx;//记录路径上的坐标 (入栈)
				s[k++].y = ty; //记录路径上的坐标(入栈)
				DSF(tx, ty, k + 1);//前往下一个点
				flag[tx][ty] = 0;//回溯（走过的路退回）
				k--;//出栈
			}
		}
	}
}

int main()
{
	memset(flag, 0, sizeof(flag));//标志数组置零
	oldMap();//输出原图
	findAim();//寻找目标点
	DSF(Beginx, Beginy, 0);//神搜最短路径
	Output();//输出最短路径
	return 0;
}