一本通-1252：走迷宫（迷宫型BFS）

【题目描述】 一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

【输入】 第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C ≤ 40)

接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。

空地格子用‘.’表示，有障碍物的格子用‘#’表示。

迷宫左上角和右下角都是‘.’。

【输出】 输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

【输入样例】 5 5 ..###

....

.#.

.#.

.#..

【输出样例】 9

---

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int x, y;
    Node(int xEle, int yEle): x(xEle), y(yEle) {}
};

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


void BFS()
{
    path[startX][startY] = 1;
    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 row = tmp.x + direction[i][0];
            int col = tmp.y + direction[i][1];
            if (0 <= row && row < m && 0 <= col && col < n && grid[row][col] == '.') {
                grid[row][col] = '#';
                path[row][col] = path[tmp.x][tmp.y] + 1;
                q.push(Node(row, col));
            }
        }
    }

    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];
        }
    }

    startX = startY = 0;
    endX = m - 1; endY = n - 1;
    BFS();

    return 0;
}