题目描述

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。

叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。

迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。

现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。

现在要求你来帮助他实现这个目标。

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

样例

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#.@.## 
.#..#. 
0 0

10
8
-1

算法

BFS

1. 初始化dist距离矩阵的时候，初值是-1或0x3f都是可以的，我都AC了
2. 方向数组，也就是偏移量的使用，非常滴粽药！QAQ
3. 可以先把不符合条件的写出来，直接continue，这些条件的列出并无先后次序

   • 第一个，if(x < 0 || x >= n || y < 0 || y >= m)，我一开始把||写成了&&，其实不对，怎么可能x < 0的同时还>= n
   • 第二个，if(dist[x][y] != 0x3f3f3f3f)，也就是这个格子如果走过的话，直接continue
   • 第三个，if(g[x][y] == '#') continue;，题目限制，理解题意就好

4. 然后，则是如果下个格子可以走，也分2种情况（有先后次序）

   • 下一个格子是终点，直接return d[x][y]，然而前提是要先计算dist[x][y] = dist[t.x][t.y] + 1，不能还没计算就return
   • 下一个格子是终点，那就老老实实地dist[x][y] = dist[t.x][t.y] + 1，然后将这个点push进队列q中。

5. 最后，如果整个队列q都空了，还没找到答案，说明无解，return -1即可。
6. 加一句，一开始要遍历找到起点st，这个是依据题目而定的。

时间复杂度

$O(nm)$

n和m分别为图的行数和列数

如果上面的时间复杂度分析错了希望大佬可以指出谢谢~

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 310;

typedef pair<int, int> PII;

#define x first     // **1
#define y second

int n, m;
char g[N][N];
int dist[N][N];
PII st, ed;

int bfs(PII st)
{
    memset(dist, 0x3f, sizeof dist);
    // memset(dist, -1, sizeof dist);

    queue<PII> q;
    q.push(st);
    dist[st.x][st.y] = 0;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int x = t.x + dx[i], y = t.y + dy[i];

            if(dist[x][y] != 0x3f3f3f3f) continue;

            // if(x < 0 && x >= n && y < 0 && y >= m) continue;
            if(x < 0 || x >= n || y < 0 || y >= m) continue;

            if(g[x][y] == '#') continue;

            // if(g[x][y] == '*') return dist[x][y];


            dist[x][y] = dist[t.x][t.y] + 1;
            if(g[x][y] == '*') return dist[x][y];  // **2
            q.push({x, y});
        }
    }

    return -1;
}

int main()
{
    while(cin >> n >> m, n || m)
    {
        for(int i = 0; i < n; i ++) cin >> g[i];

        for(int i = 0; i < n; i ++)
            // for(int j = 0; j < n; j ++)  // **3
            for(int j = 0; j < m; j ++)
                if(g[i][j] == '@')
                    st = {i, j};

        cout << bfs(st) << endl;
    }

    return 0;
}