一本通-1251：仙岛求药（迷宫类型的BFS）¶

【题目描述】少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

下图显示了一个迷阵的样例及李逍遥找到仙药的路线。

【输入】输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:

1)‘@’：少年李逍遥所在的位置；

2)‘.’：可以安全通行的方格；

3)‘#’：有怪物的方格；

4)‘*’：仙药所在位置。

当在一行中读入的是两个零时，表示输入结束。

【输出】对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。

【输入样例】 8 8 .@##...#

....#.¶

.#.##..¶

..#.###.

.#...#.¶

..###.#. ...#... .#...### 6 5 ..#. .#... ..##. ..... .#... ....@ 9 6

.#..#. .#.*.# .####. ..#... ..#... ..#... ..#...

.@.¶

.#..#. 0 0

【输出样例】 10 8

-1

#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(25, vector<char>(25));
vector<vector<int> > path(25, vector<int>(25, 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 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));
            }
        }
    }

    if (path[endX][endY] == INT_MAX) cout << (-1) << endl;
    else cout << path[endX][endY] << endl;
}


void init()
{
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            path[i][j] = INT_MAX;
        }
    }
}

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

    while ((cin >> m >> n) && (m || n)) {
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> grid[i][j];
                if (grid[i][j] == '@') {
                    startX = i; startY = j;
                }
                else if (grid[i][j] == '*') {
                    grid[i][j] = '.';
                    endX = i; endY = j;
                }
            }
        } 

        BFS();
        init();
    }

    return 0;
}

这道题目里面要求计算初始的位置的方格，但是从结果来看它并没有计算初始方格，所以还是直接用