利用图的深度优先搜索解决迷宫问题

总体思路是：从（1，1）出发，分四个方向深度优先搜索，将访问过的点的访问标志置为3，如果从当前点出发无法找到出口，则将该点的访问标志置为2。输出结果是如果标志为3的就输出L，其他标志的就输出2，这样就能很清楚的看到从入口到出口的路径了
完整代码如下：

/*
	利用图的深度优先搜索解决迷宫问题 
*/

#define N 10
int maze[N][N] = {{0}, {0, 0, 0, 0, 0, 0, 0, 0, 0},
     {0, 0, 1, 1, 1, 1, 0, 1, 0}, {0, 0, 0, 0, 0, 1, 0, 1, 0},
     {0, 0, 1, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 0, 1, 0},
     {0, 0, 1, 0, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 0, 0},
     {0, 0, 1, 1, 1, 1, 1, 1, 0}};// 每个点三种状态，0表示有路可走，1表示墙壁，无路可走，-1表示已经走过 
//int maze[N][N] = {{0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, 
//					   {0, 0, 0, 1, 1}, {0, 1, 0, 0, 0}};
int dirX[4] = {1, -1, 0, 0};
int dirY[4] = {0, 0, 1, -1};
     
#include<iostream>
using namespace std;

void DFS(int x, int y);
bool checkDir(int x, int y);
void outputPath(); 

int main() {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++)
			cout << maze[i][j] << " ";
		cout << endl;
	}
	maze[1][1] = 3;
	DFS(1, 1);
	
	return 0;
}

void DFS(int x, int y) {
	for (int dir = 0; dir < 4; dir++) {// 向上下左右四个方向搜索 
		// 得到接下来访问的点 
		int newX = x + dirX[dir]; 
		int newY = y + dirY[dir];
		
		if (checkDir(newX, newY)) {
			maze[newX][newY] = 3; 
			if (newX == 8 && newY == 8)// 判断是否到了出口 
				outputPath();// 输出入口到出口的路径 
			else
				DFS(newX, newY); // 往下深度搜索 
		}
	}	
	maze[x][y] = 2;// 如果当前点往四个方向搜索都没有找到出口，那么就置为2 
}

bool checkDir(int x, int y) {
	if (x < 1 || x > 8 || y < 1 || y > 8 || maze[x][y] != 0)
		return false;	
	else 
		return true;
}

void outputPath() {
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			if (maze[i][j] == 3)
				cout << "L";
			else 
				cout << "*";
		}
		cout << endl;
	}
}

再贴个运行结果