迷宫问题 （C语言代码）

参考代码:

#include<stdio.h>

// 最大行列数
#define MAXRCS 100
#define MAXVAL 0xffff

int map[MAXRCS][MAXRCS]; // 用整型数组存放地图并可记录步数

// 起点终点坐标、行列数
int sx, sy, ex, ey, r, c;
// 四个方向移动
int xp[] = { 0, 1, 0, -1 };
int yp[] = { 1, 0, -1, 0 };

void DFS(int x, int y, int step) {

	int i, nx, ny;

	// 四个方向
	for (i = 0; i < 4; i++) {

		nx = x + xp[i];
		ny = y + yp[i];

		// 坐标在地图内 ----------------------- 下一步步数比原先路线少(为可通点)
		if (nx >= 0 && nx < r && ny >= 0 && ny < c && step + 1 < map[nx][ny]) {

			map[nx][ny] = step + 1;
			DFS(nx, ny, step + 1);
		}
	}
}

int main() {

	int i, j, t;
	char ch;

	scanf("%d", &t);

	while (t--) {

		// 初始化地图
		scanf("%d%d", &r, &c);
		getchar(); // 读取'\n'
		for (i = 0; i < r; i++) {

			for (j = 0; j < c; j++) {

				ch = getchar(); // 读取字符并转换，0不可通，MAXVAL为可通
				switch (ch) {

				case '-': { map[i][j] = MAXVAL; break; }
				case '#': { map[i][j] = 0; break; }
				case 'S': { map[i][j] = 0; sx = i; sy = j; break; }
				case 'E': { map[i][j] = MAXVAL; ex = i; ey = j; }
				}
			}
			getchar();
		}

		DFS(sx, sy, 0); // map[ex][ey]值改动，说明有可达路径
		printf("%d\n", map[ex][ey] != MAXVAL ? map[ex][ey] : -1);
	}
	return 0;
}

示意图：（红色表压栈）

原地图：--------->  转换后：---------->  一次深搜后：----->  回溯，只走步数更少的路线：