|
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> maze(n);
for (int i = 0; i < n; i++) {
cin >> maze[i];
}
// 初始化距离数组,-1表示未访问
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
int sx = -1, sy = -1; // 起点坐标
// 寻找起点S的位置
bool found = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
sx = i;
sy = j;
found = true;
break;
}
}
if (found) break;
}
// 方向数组:上下左右
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// 起点入队,并设置距离为0
dist[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int step = dist[x][y];
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 检查新位置是否在迷宫范围内
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// 如果是墙或已访问过,则跳过
if (maze[nx][ny] == '#' || dist[nx][ny] != -1)
continue;
// 如果找到终点,输出步数并结束
if (maze[nx][ny] == 'T') {
cout << step + 1 << endl;
return 0;
}
// 更新距离并入队
dist[nx][ny] = step + 1;
q.push({nx, ny});
}
}
}
// 如果无法到达终点,输出-1
cout << -1 << endl;
return 0;
} |
|