地、颜色、魔法

题意

给定一个n * m的字符矩阵，问有多少个.不能通过相邻的.和边界相连，还得加上#的数量，问这个总和。

题解

从边界开始dfs标记一下和边界相连的.就行了，然后把没有被标记的.的数量求一下，然后加上#的数量即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7;
int n, m, vis[N]; char s[N], t[N];
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(int p) {
    if (vis[p] || s[p] == '#') return;
    vis[p] = 1;
    for (int i = 0; i < 4; i++) {
        int dx = dir[i][0] + p / m, dy = dir[i][1] + p % m;
        if (dx >= 0 && dx < n && dy >= 0 && dy < m && s[dx * m + dy] == '.')
            dfs(dx * m + dy);
    }
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", t);
        for (int j = 0; j < m; j++) {
            s[i * m + j] = t[j];
        }
    }
    s[n * m] = 0;
    for (int i = 0; i < n; i++) dfs(i * m);
    for (int i = 0; i < m; i++) dfs(i);
    for (int i = 0; i < n; i++) dfs(i * m + m - 1);
    for (int i = 0; i < m; i++) dfs(m * (n - 1) + i);
    int ret = 0;
    for (int i = 0; i < n * m; i++) {
        if (s[i] == '#' || !vis[i]) ret++;
    }
    printf("%d\n", ret);
}
int main() {
    solve();
    return 0;
}