Coronavirus

题目：Coronavirus
来源：哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛）

解题思路

多多从家中 S 出发，每次可以向上、下、左、右四个方向移动。多多不会通过高危地段自身 * 及其八个方向的地段。
请问他能顺利到达超市 E 吗？如果能的话输出最短路径长度，否则输出 "Impossible"。

ground 表示地图，d 表示方向，dangers 表示高危地点，sx, sy 表示出发地点。
len 表示最短路径。

使用 BFS 算法。广度遍历地图，要么到达 E，要么无路可走。

C++代码

#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;

int d[8][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {-1,-1}, {-1,1}, {1,-1}};
int N, M;
int sx, sy;
set<pair<int, int>> dangers;

int bfs(vector<vector<char>>& ground){
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    queue<pair<int,int>> que;
    que.push(make_pair(sx, sy));
    visited[sx][sy] = true;
    int len = 1;
    int cnt = que.size();
    while(!que.empty()){
        int nx = que.front().first;
        int ny = que.front().second;
        que.pop();
        --cnt;
        for(int i=0; i<4; ++i){
            int x = nx + d[i][0];
            int y = ny + d[i][1];
            if(x>=0 && x<N && y>=0 && y<M && visited[x][y]==false){
                auto p = make_pair(x,y);
                if(dangers.find(p)==dangers.end()){
                    if(ground[x][y] == 'E')
                        return len;
                    que.push(p);
                }
                visited[x][y] = true;
            }
        }
        if(cnt == 0){
            ++len;
            cnt = que.size();
        }
    }
    return -1;
}

int main(){
    cin >> N >> M;
    vector<vector<char>> ground(N, vector<char>(M));
    for(int i=0; i<N; ++i){
        for(int j=0; j<M; ++j){
            cin >> ground[i][j];
            if(ground[i][j] == 'S'){
                sx = i;
                sy = j;
            }
            else if(ground[i][j] == '*'){
                dangers.insert(make_pair(i,j));
                for(int k=0; k<8; ++k){
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    dangers.insert(make_pair(x,y));
                }
            }
        }
    }

    int len = bfs(ground);
    if(len == -1)
        cout << "Impossible" << endl;
    else
        cout << len << endl;
    return 0;
}