【学习记录】C++迷宫问题

给定一个大小为NxM的迷宫。迷宫有通道和墙壁组成，每一步可以向邻接的上下左右四格通道移动。请求从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点，其中 

样例：

N=10,M=10 (‘#’,’.’,’S’,’G’分别表示墙壁、通道、起点和终点)

#S######.#

......#..#

.#.##.##.#

.#........

##.##.####

....#....#

.#######.#

....#.....

.####.###.

....#...G#

输出：

 22

提示：为便于测试和修改，迷宫数据可以采用文本文件的形式进行保存，程序运行时从文件读入。

程序代码及测试结果：

#include 
using namespace std;

char map[10][10] = {0};

int flag[10][10] = {0}; //0为未访问，1为已访问
void dfs(int x, int y, int step);
int Min = 100;

int main() {
	int M, N;
	int i, j, x, y, step = 0;
	cin >> M >> N;
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			cin >> map[i][j];
		}
		cout << endl;
	}
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (map[i][j] == 'S') {
				x = i;
				y = j;
			}
		}
	}
	flag[x][y] = 1;
	dfs(x, y, step);
	printf("%d", Min);
	return 0;
}

void dfs(int x, int y, int step) {
	if (map[x][y] == 'G') {

		if (step < Min)
			Min = step;
		return;
	}
	if (map[x - 1][y] != '#' && flag[x - 1][y] == 0 && x - 1 >= 0) {
		flag[x - 1][y] = 1;
		dfs(x - 1, y, step + 1);
		flag[x - 1][y] = 0;
	}
	if (map[x + 1][y] != '#' && flag[x + 1][y] == 0 && x + 1 <= 9) {
		flag[x + 1][y] = 1;
		dfs(x + 1, y, step + 1);
		flag[x + 1][y] = 0;
	}
	if (map[x][y - 1] != '#' && flag[x][y - 1] == 0 && y - 1 >= 0) {
		flag[x][y - 1] = 1;
		dfs(x, y - 1, step + 1);
		flag[x][y - 1] = 0;
	}
	if (map[x][y + 1] != '#' && flag[x][y + 1] == 0 && y + 1 <= 9) {
		flag[x][y + 1] = 1;
		dfs(x, y + 1, step + 1);
		flag[x][y + 1] = 0;
	}
	return;
}

2022/5/15