题解 | #病菌感染#

简单的多路广搜。

将最初病菌放入队列，之后依次出列，判断其向外蔓延的格子是否可以被病菌覆盖，可以被覆盖将其放入队列，否则不做操作。

代码：

void solve() {
    int n,m; cin>>n>>m;
    // 按 从 0 到 n-1 进行建图
    vector<vector<int>> ph(n, vector<int>(n)), vis(ph);
    queue<PII> q; // pair<int,int> ==> x,y
    rep(i,1,m) {
        int tx,ty; cin>>tx>>ty;
        tx--,ty--;
        vis[tx][ty] = 1;
        q.push({tx,ty});
    }
    // 方向
    vector<int> fx({1,-1,0,0}), fy({0,0,1,-1});
    // 判断是否这个格子有两个以上相邻的病菌格子
    auto check = [&](int x,int y) -> bool {
        int cnt = 0;
        rep(i,0,3) {
            int xx = x + fx[i], yy = y + fy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
            if(vis[xx][yy]) cnt++;
        }
        return cnt >= 2;
    };
    
    // bfs
    while(q.size()) {
        auto tmp = q.front(); q.pop();
        int x = tmp.vf, y = tmp.vs;
        rep(i,0,3) {
            int xx = x + fx[i], yy = y + fy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
            if(vis[xx][yy]) continue;
            if(check(xx,yy)) {
                vis[xx][yy] = 1;
                q.push({xx,yy});
            }
        }
    }
    bool fg = false;
    rep(i,0,n-1) {
        rep(j,0,n-1) {
            if(vis[i][j] == 0) fg = true;
        }
    }
    puts(!fg ? "YES" : "NO");
}