一本通-1254：走出迷宫（二维迷宫型BFS）

【题目描述】 当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。

【输入】 第一行是两个整数n和m(1≤n,m≤100)，表示迷宫的行数和列数。

接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。

【输出】 输出从起点到出口最少需要走的步数。

【输入样例】 3 3 S#T .#. ...

【输出样例】 6

---

这道题其实存在一点疑问，是否一定可以到达终点，题目并未说清，那就默认可以到达吧，然后就是一个简单的二维BFS。

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int x, y;
    Node(int a, int b): x(a), y(b) {}   
};

int m, n;
vector<vector<char> > grid(105, vector<char>(105));
vector<vector<int> > path(105, vector<int>(105, INT_MAX));
int startX, startY, endX, endY;
int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


void BFS()
{
    path[startX][startY] = 0;
    grid[startX][startY] = '#';
    queue<Node> q;
    q.push(Node(startX, startY));

    while (!q.empty()) {
        Node tmp = q.front(); q.pop();

        if (tmp.x == endX && tmp.y == endY) break;

        for (int i = 0; i < 4; ++i) {
            int nextRow = tmp.x + direction[i][0];
            int nextCol = tmp.y + direction[i][1];
            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && grid[nextRow][nextCol] == '.') {
                path[nextRow][nextCol] = path[tmp.x][tmp.y] + 1;
                grid[nextRow][nextCol] = '#';
                q.push(Node(nextRow, nextCol));
            }
        }
    }

    cout << path[endX][endY] << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> n;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];

            if (grid[i][j] == 'S') {
                startX = i; startY = j;
            }
            else if (grid[i][j] == 'T') {
                endX = i; endY = j;
                grid[i][j] = '.';
            }
        }
    }

    BFS();

    return 0;
}