迷宫问题 （C语言代码）

解题思路:

    第一次写，理理思路。

    1、采用广度优先搜索，先让起点入队；

    2、队列首端出队，将下一步可达位置入队，并标记距离为上一步的距离 + 1；

    3、当队列不为空时循环2过程，最后得到结果。

注意事项:

    1、因为是广度优先遍历，各条路线的距离层层递增，最先找到终点的为最短路径，即可返回；

    2、在某位置向四周查找下一可达位置时，既要判断在边界内且可通，也要判断是否为已经进行过此操作的位置，防止重复。

参考代码:

#include<stdio.h>
#include<string.h>

// 最大行列数
#define MAXRCS 100

// 迷宫地图结构体，sign数组列数 + 1，存放'\0'
typedef struct MazeMap {
	char sign[MAXRCS][MAXRCS + 1]; // 标志
	int step[MAXRCS][MAXRCS]; // 目前步数
} MazeMap;

// 入口出口坐标
int sx, sy, ex, ey;
// 上下左右移动
int xp[] = { -1, 1, 0, 0 };
int yp[] = { 0, 0, -1, 1 };

int BFSTraverse(MazeMap *map, int n, int m) {

	// 有多少可通点，进队元素就有多少个
	int queuex[MAXRCS * MAXRCS], queuey[MAXRCS * MAXRCS];
	int front = 0, rear = 0, tx, ty, nx, ny;

	// 将入口坐标入队
	queuex[rear] = sx;
	queuey[rear++] = sy;
	map->step[sx][sy] = 1; // 与未做出尝试的坐标区别开，取1，最后再减去

	// 队列不为空时循环，即还有通路
	while (front != rear) {

		tx = queuex[front];
		ty = queuey[front++];

		if (tx == ex && ty == ey) {
			
			return map->step[ex][ey] - 1;
		}

		for (int i = 0; i < 4; i++) {

			nx = tx + xp[i];
			ny = ty + yp[i]; // 向四周做出尝试

			// 下一步的坐标在地图内 ------------------ 为通路 ----------------- 未在此坐标向四周做出尝试
			if (nx >= 0 && ny >= 0 && nx < n && ny < m && map->sign[nx][ny] != '#' && map->step[nx][ny] == 0) {

				queuex[rear] = nx;
				queuey[rear++] = ny; // 为通路且未尝试过，进队
				map->step[nx][ny] = map->step[tx][ty] + 1; // 到此处步数 + 1 （也标记了此处做出了尝试）
			}
		}
	}

	return -1; // 到此处说明无可达路径
}

int main() {

	MazeMap map;
	int t, n, m;
	scanf("%d", &t);
	
	while (t--) {

		// 清空迷宫地图
		memset((void *)&map, 0, sizeof(map));

		// 初始化迷宫
		scanf("%d%d", &n, &m);
		scanf("%*[^\n]"); scanf("%*c");
		for (int i = 0; i < n; i++) {
			gets(map.sign[i]);
		}

		// 确定迷宫入口出口
		for (int i = 0; i < n; i++) {

			for (int j = 0; j < m; j++) {

				if (map.sign[i][j] == 'S') {
					sx = i;
					sy = j;
				}
				if (map.sign[i][j] == 'E'){
					ex = i;
					ey = j;
				}
			}
		}

		// 广度优先遍历
		int res = BFSTraverse(&map, n, m);
		printf("%d\n", res);
	}
	return 0;
}