题目描述

难度分:$2400$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n \times m$之和$\leq 4 \times 10^5$。

每组数据输入$n$，$m(2 \leq n,m \leq 2 \times 10^5$且$n \times m \leq 4 \times 10^5$)和$n$行$m$ 列的网格图，其中#表示仙人掌，.表示空地。

你需要在空地上种植仙人掌，使得不存在一条从第一行到最后一行的只包含空地的路径（只能上下左右走）。

种植仙人掌时，不能种在已有仙人掌的旁边（上下左右）。注：输入的网格图保证不存在上下左右相邻的仙人掌。

你不能移除仙人掌，请种植最少数量的仙人掌以满足要求。

如果可以做到，输出YES和具体方案；如果无法做到，输出NO。

输入样例

4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...

输出样例

YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...

算法

01$BFS$

分析

图论问题主要就是难在识别出它是个图论问题，然后建模，本题就发扬光大了这个特点。如果去考虑怎么从空地上走，那会一头雾水，不知道怎么下手。

由于不能在已有仙人掌的上下左右种植新的仙人掌，因此只能斜着种。此时发现只要能从左往右种出一堵仙人掌的墙，就肯定不存在一条从第一行到最后一行的空地路径。此时我们考虑怎么种仙人掌，题目要求种的仙人掌数量最少，那这个从左往右的仙人掌墙就要尽可能地多穿过已有的仙人掌。

最短路问题

这样一来题目就转换成了一个最短路问题，求从第$0$列出发到第$m-1$列的最短距离。如果经过的格子是#，说明走的是原有的仙人掌，边权为$0$；如果经过的格子是.，说明是空地，可以种新的仙人掌，边权为$1$。而只有$0$和$1$两种边权就能让我们想到01$BFS$，接下来利用它来求最短路。

考虑到在有解的情况下，最后还要推出具体方案，所以在进行01$BFS$的过程中对于每个格点位置$(i,j)$，还需要记录它是从哪个位置转移过来的，用一个$pre$数组来存储每个位置是走哪个方向转移过来的就行。01$BFS$完成后再从终点位置利用$pre$数组倒推回去就能得到仙人掌墙中所有仙人掌的位置。

复杂度分析

时间复杂度

01$BFS$的时间复杂度是线性的，为$O(nm)$。算法的时间复杂度瓶颈就在于此，因此这也是算法整体的时间复杂度。

空间复杂度

求最短路需要的距离数组$dist$，以及倒推方案所需要的$pre$数组都是$O(nm)$级别的。再算上01$BFS$的双端队列开销，在最差情况下需要入队$O(nm)$个格点的位置。因此，算法的额外空间复杂度为$O(nm)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;
typedef pair<int, int> PII;

const int N = 200010, INF = 0x3f3f3f3f;
vector<int> pre[N], dist[N];
string grid[N];
int t, n, m;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int dr[4] = {-1, -1, 1, 1}, dc[4] = {-1, 1, -1, 1};

// 检查(x,y)位置能不能种仙人掌，不能越界，也不能是已有仙人掌的上下左右邻居
bool check(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m) {
        return false;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '#') {
            return false;
        }
    }
    return true;
}

void solve() {
    for(int i = 0; i < n; i++) {
        dist[i].clear();
        pre[i].clear();
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            dist[i].push_back(INF);
            pre[i].push_back(-1);
        }
    }
    deque<PII> q;
    for(int i = 0; i < n; i++) {
        if(grid[i][0] == '#') {
            q.push_front({i, 0});
            dist[i][0] = 0;
        }else if(check(i, 0)) {
            q.push_back({i, 0});
            dist[i][0] = 1;
        }
    }
    while(!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        for(int i = 0; i < 4; i++) {
            int nx = x + dr[i], ny = y + dc[i];
            if(check(nx, ny)) {
                int w = grid[nx][ny] == '.'? 1: 0;
                if(dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    pre[nx][ny] = i;     // 记录(nx,ny)是从哪个方向转移过来的
                    if(w == 1) {
                        q.push_back({nx, ny});
                    }else {
                        q.push_front({nx, ny});
                    }
                }
            }
        }
    }
    int ans = INF, min_row;
    for(int i = 0; i < n; i++){
        if(dist[i][m - 1] < ans){
            ans = dist[i][m - 1];
            min_row = i;
        }
    }
    if(ans == INF){
        puts("NO");
        return;
    }
    puts("YES");
    int x = min_row, y = m - 1;
    while(true) {
        grid[x][y] = '#';
        int dir = pre[x][y];
        if(dir == -1) break;
        x -= dr[dir], y -= dc[dir];
    }
    for(int i = 0; i < n; i++) {
        cout << grid[i] << endl;
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++) {
            cin >> grid[i];
        }
        solve();
    }
    return 0;
}