迷宫问题 （C++代码）

解题思路:

        利用了C++ STL queue 模板类（队列）简单介绍一下

queue.push(Next) Next 元素压入列尾

queue.pop()      队首元素出列

queue.front()    访问队首元素

queue.empty()     若队列为空 返回 true

        广度优先搜索思想，每一步只搜索能够达到的所有点，在求最小路径的题型里，第一个找到的解就是最优

解，利用到队列先进先出的特点。    

        ( 下面还有深搜超时版本。20*20 以下的图大概可以拿来用，这题是100*100 )

参考代码:

#include<bits/stdc++.h>
using namespace std;

char Map[100][100];            /*    存储图    */
bool vis[100][100];            /* 标记走过的点 */
bool finds = false;            /*   是否找到   */
int  map_high, map_width;      /*    图边界    */
int  moveX[4] = { -1,0,1,0 };  /*   四个方向   */
int  moveY[4] = { 0,-1,0,1 };

struct status {                /* 存储当前状态 */
	int X, Y, step;
};

bool check(status next) {      /*   剪枝条件   */
	if (next.X >= 0 && next.X < map_high)
		if (next.Y >= 0 && next.Y < map_width)
			if (Map[next.X][next.Y] != '#' && vis[next.X][next.Y] != true)
				return true;
	return false;
}

void BFS(status start) {
	queue<status> Search;                   /*     定义队列     */
	Search.push(start);                     /*     起点入列     */
	while (!Search.empty()) {               /*  不为空就一直搜  */
		status now = Search.front();        /*    访问队首元素  */
		if (Map[now.X][now.Y] == 'E') {     /*       出口       */
			finds = true;
			cout << now.step << endl;
			return;
		}
		status next;                        /*   四个方向拓展   */
		for (int i = 0; i < 4; i++) {
			next.X = now.X + moveX[i];
			next.Y = now.Y + moveY[i];
			next.step = now.step + 1;

			if (check(next) == true) {      /*      合法点      */
				vis[next.X][next.Y] = true; /*    标记，入列    */
				Search.push(next);
			}
		}
		Search.pop();                       /*   队首元素出列   */
	}
	if (finds == false)
		cout << -1 << endl;
}

int main() {
	int num; cin >> num;
	while (num--) {
		/*             初始化图              */
		memset(Map, 0, sizeof(Map)); memset(vis, false, sizeof(vis));
		cin >> map_high >> map_width; cin.get();
		for (int i = 0; i < map_high; i++) {
			gets(Map[i]);
		}
		
		/*              寻找起点            */
		bool first = false;
		int positiom1, positiom2;
		for (positiom1 = 0; positiom1 < map_high; positiom1++) {
			for (positiom2 = 0; positiom2 < map_width; positiom2++)
				if (Map[positiom1][positiom2] == 'S') {
					first = true; break;
				}
			if (first == true) break;
		}

		/*            初始化起点            */
		status start; 
		start.X = positiom1;
		start.Y = positiom2;
		start.step = 0;
		vis[start.X][start.Y] = true;
		finds = false;

		BFS(start);
	}
	return 0;
}

深度优先搜索超时版：

#include<bits/stdc++.h>
using namespace std;

char Map[105][105];
bool vis[105][105];
int  map_high, map_width;
int  moveX[4] = { -1,0,1,0 };
int  moveY[4] = { 0,-1,0,1 };
int  minstep = 9999;

struct status {
	int X, Y;
};

void DFS(int X, int Y, int step) {
	if (Map[X][Y] == 'E') {
		if (step < minstep) minstep = step;
		return;
	}

	for (int i = 0; i < 4; i++) {
		status moving;
		moving.X = X + moveX[i];
		moving.Y = Y + moveY[i];
		if (moving.X >= 0 && moving.Y >= 0 && moving.X < map_high &&
			moving.Y < map_width && vis[moving.X][moving.Y] != true &&
			Map[moving.X][moving.Y] != '#') {

			vis[moving.X][moving.Y] = true;
			DFS(moving.X, moving.Y, step + 1);
			vis[moving.X][moving.Y] = false;
		}
	}
}

int main() {
	int data;
	cin >> data;
	while (data--) {
		cin >> map_high >> map_width; cin.get();
		for (int i = 0; i < map_high; i++) {
			gets(Map[i]);
		}
		bool start = false;
		int positiom1, positiom2;
		for (positiom1 = 0; positiom1 < map_high; positiom1++) {
			for (positiom2 = 0; positiom2 < map_width; positiom2++)
				if (Map[positiom1][positiom2] == 'S') {
					start = true; break;
				}
			if (start == true) break;
		}
		vis[positiom1][positiom2] = true;
		DFS(positiom1, positiom2, 0);

		if (minstep == 9999) cout << -1 << endl;
		else cout << minstep << endl;
	}
	return 0;
}

- End