BFS-走出迷宫
走出迷宫
总时间限制: 1000ms 内存限制: 65536kB
描述
当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。
输入
第一行是两个整数n和m(1<=n,m<=100)，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点,'T'表示出口。
输出
输出从起点到出口最少需要走的步数。
样例输入
3 3
S#T
.#.
...
样例输出
6
题解:
// 走出迷宫
#include
#include
#include
using namespace std;
const int N = 110; // 最大大小
char maze[110][110]; // 迷宫数组
bool visited[110][110]; // 标记是否访问过
// 方向数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
// 结点信息
struct node
{
int x; // 横坐标
int y; // 纵坐标
int steps; // 已经走的步数
node(int xx, int yy, int ss) : x(xx), y(yy), steps(ss) {}
};
int main()
{
int n, m;
cin >> n >> m;
queue
// 初始化
memset(maze, '#', sizeof(maze));
memset(visited, false, sizeof(visited));
for (int i = 1; i <= n; ++i) // 描边输入
{
for (int j = 1; j <= m; ++j)
{
cin >> maze[i][j];
if (maze[i][j] == 'S')
{
q.push(node(i, j, 0));
visited[i][j] = true;
}
}
}
// 进行bfs
while (!q.empty())
{
node temp = q.front();
q.pop(); // 取队头
if (maze[temp.x][temp.y] == 'T') // 判定是否到达出口
{
cout << temp.steps << endl;
break;
}
// 四方向遍历
for (int i = 0; i < 4; ++i)
{
int nx = temp.x + dx[i];
int ny = temp.y + dy[i];
if (maze[nx][ny] == 'T' && !visited[nx][ny]) // 找到出口,出口也入队
{
q.push(node(nx, ny, temp.steps + 1));
visited[nx][ny] = true;
}
if (maze[nx][ny] == '.' && !visited[nx][ny]) // 找路走
{
q.push(node(nx, ny, temp.steps + 1));
visited[nx][ny] = true;
}
}
}
return 0;
}
非常经典的BFS题.
