题目描述

难度分:$1700$

输入$n$，$m(1 \leq n,m \leq 50)$和一个$n$行$m$列的网格图$grid$，仅包含#和.。

输入保证图中任意两个#都可以通过四方向移动互相到达（连通图）。

输入保证至少有一个#。

你需要把尽量少的#修改成.，使得网格图不连通。

如果无法做到，输出$-1$，否则输出最少修改次数。

注：规定空集（没有#）视作连通图，只有一个#也视作连通图。

输入样例$1$

5 4
####
#..#
#..#
#..#
####

输出样例$1$

2

输入样例$2$

5 5
#####
#...#
#####
#...#
#####

输出样例$2$

2

样例$2$图

算法

脑筋急转弯+DFS暴搜

如果#的个数小于$3$，那么无法分成多个连通块，输出$-1$，否则肯定有解。然后就发现一个问题，最多操作两次，一定可以把图弄的不连通，分为以下两种情况：

1. 对于角落的#，可以把它相邻的两个#改成.使得图不连通，所以至多操作$2$次。

2. 如果角落没有#，一定存在一个边上的#至多有两个.邻居，所以也至多操作$2$次。

所以遍历矩阵，对于每个$grid[i][j]=$#的位置$(i,j)$，删除它之后再找一个#作为起点进行DFS，能搜遍矩阵中所有的#就说明需要操作两次，否则就只需要操作一次。

复杂度分析

时间复杂度

遍历矩阵的时间复杂度为$O(nm)$，对于每个$grid[i][j]=$#的位置$(i,j)$都进行一次DFS，时间复杂度为$O(nm)$。因此，算法总的时间复杂度为$O(n^2m^2)$。

空间复杂度

DFS需要一个与输入矩阵$grid$规模相同的标记数组$st$，避免走重复的位置，因此额外空间复杂度为$O(nm)$。

C++ 代码

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

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

const int N = 55;
int n, m;
char grid[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];

int dfs(int x, int y) {
    st[x][y] = true;
    int t = 1;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(1 <= nx && nx <= n && 1 <= ny && ny <= m && grid[nx][ny] == '#' && !st[nx][ny]) {
            t += dfs(nx, ny);
        }
    }
    return t;
}

int main() {
    scanf("%d%d", &n, &m);
    int cnt = 0;
    vector<PII> pos;
    for(int i = 1; i <= n; i++) {
        scanf("%s", grid[i] + 1);
        for(int j = 1; j <= m; j++) {
            if(grid[i][j] == '#') {
                pos.push_back({i, j});
                cnt++;
            }
        }
    }
    if(cnt < 3) {
        puts("-1");
        exit(0);
    }
    if(dfs(pos[0].first, pos[0].second) != cnt) {
        puts("0");
        exit(0);
    }
    int ans = 2;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(grid[i][j] == '#') {
                memset(st, 0, sizeof st);
                st[i][j] = true;
                int x, y;
                if(pos[0].first == i && pos[0].second == j) {
                    x = pos[cnt - 1].first, y = pos[cnt - 1].second;
                }else {
                    x = pos[0].first, y = pos[0].second;
                }
                if(dfs(x, y) != cnt - 1) {
                    ans = 1;
                    break;
                }
            }
        }
        if(ans == 1) break;
    }
    printf("%d\n", ans);
    return 0;
}