迷宫问题 （C++代码）

解题思路:

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#define N 100

using namespace std;

char map[N + 2][N + 2];
bool vis[N + 2][N + 2];
int totalStep;

int rowDir[] = { -1,0,1,0 };
int colDir[] = { 0,1,0,-1 };

class Node
{
public:
	int row, col, step;
	Node(int row, int col, int step);
};

Node::Node(int row, int col, int step): row(row),col(col),step(step) { }

void init(int n, int m)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			vis[i][j] = false;
			map[i][j] = '\0';
		}
	}

}

pair<int, int> getStart(int n, int m)
{
	pair<int, int> start;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == 'S')
			{
				start.first = i;
				start.second = j;
				break;
			}
		}
	}
	return start;
}

bool BFS(int startRow, int startCol, int n, int m)
{
	queue<Node> Q;
	Node root(startRow, startCol, 0);
	Q.push(root);
	vis[startRow][startCol] = true;

	while (!Q.empty())
	{
		Node node = Q.front();
		Q.pop();
		int curRow = node.row;
		int curCol = node.col;

		if (map[curRow][curCol] == 'E')
		{
			totalStep = node.step;
			return true;
		}

		for (int i = 0; i < 4; i++)
		{
			int newRow = curRow + rowDir[i];
			int newCol = curCol + colDir[i];
			if (newRow >= 1 && newRow <= n && newCol >= 1 && newCol <= m && map[newRow][newCol] != '#' && !vis[newRow][newCol])
			{
				Node newNode(newRow, newCol, node.step + 1);
				Q.push(newNode);
				vis[newRow][newCol] = true;
			}
		}
	}
	return false;
}

int main(int argc, char** argv)
{
	int time = 0;
	cin >> time;

	while (time--)
	{
		int n = 0, m = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
				cin >> map[i][j];
			getchar();
		}

		pair<int, int> start = getStart(n, m);

		if (BFS(start.first, start.second, n, m))
			cout << totalStep << endl;
		else
			cout << -1 << endl;

		init(n, m);
	}

	return 0;
}