迷宫问题 （C++代码）

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1001;
char map[maxn][maxn];
int vist[maxn][maxn];
struct Node {
	int x, y, ans;
};
queue<Node> Q;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int n, m;
Node zore;
Node End;
int BFS(Node& zero, Node& End) {
	memset(vist, 0, sizeof(vist));
	vist[zore.x][zore.y] = 1;
	Q.push(zero);
	Node front;
	while (!Q.empty()) {
		front = Q.front();
		Q.pop();
		if (front.x == End.x && front.y == End.y)
		{
			return front.ans;
		}
		for (int i = 0; i < 4; i++)
		{
			int fx = front.x + dx[i];
			int fy = front.y + dy[i];
			Node v;
			v.x = fx;
			v.y = fy;
			if (fx >= 0 && fx < n && fy >= 0 && fy < m && (map[fx][fy] == '-' || map[fx][fy] == 'E') && !vist[fx][fy])
			{
				v.ans = front.ans + 1;
				vist[fx][fy] = 1;
				Q.push(v);
			}
		}
	}
	return 0;
}
int main() {
	int num;
	cin >> num;
	for (int ii = 0; ii < num; ii++)
	{
		cin >> n >> m;
		memset(map, 0, sizeof(map));
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> map[i][j];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] == 'S') {
					zore.x = i;
					zore.y = j;
				}
				if (map[i][j] == 'E') {
					End.x = i;
					End.y = j;
				}
			}
		int cnt = BFS(zore, End);
		if (cnt)
		{
			cout << cnt << endl;
		}
		else
			cout << -1 << endl;
	}
	return 0;
}

另外附上一个深搜超时版

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 101;
char map[maxn][maxn];
int vist[maxn][maxn];
int n, m;
int fx, fy;
int Min = 999999;
int temp;
int x[4] = { 0,0,-1,1 };
int y[4] = { -1,1,0,0 };
void DFS(int dx, int dy,int cnt)
{
	if (dx == fx && dy == fy)
	{
		if (cnt <= Min) Min = cnt;
		temp = 1;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int fx = dx + x[i];
		int fy = dy + y[i];
		if (map[fx][fy] == '#' || fx < 0 || fx >= n || fy < 0 || fy >= m||vist[fx][fy])
			continue;
		vist[fx][fy] = 1;
		DFS(fx, fy, cnt + 1);
		vist[fx][fy] = 0;
	}
}
int main()
{
	int dx, dy;
	int num;
	cin >> num;
	while (num--)
	{
		cin >> n >> m;
		memset(map, 0, sizeof(map));
		memset(vist, 0, sizeof(vist));
		temp = 0;
		Min = 9999;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> map[i][j];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] == 'S')
				{
					dx = i;
					dy = j;
					break;
				}
			}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (map[i][j] == 'E')
				{
					fx = i;
					fy = j;
					break;
				}
		DFS(dx, dy, 0);
		if (temp)
			cout << Min << endl;
		else
			cout << "-1" << endl;
	}
	return 0;
}