题解 | 挡住洪水

#include <bits/stdc++.h>
using namespace std;

int n, m;
char str[550][550];
int cnt;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void dfs1(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx >= 0 && ty >= 0 && tx <= x + 1 && ty <= y + 1 && str[tx][ty] == '0')
        {
            str[tx][ty] = '.';
            dfs1(tx, ty);
        }
    }
}

void dfs2(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx >= 1 && ty >= 1 && tx <= x && ty <= y && str[tx][ty] == '0')
        {
            str[tx][ty] = '*';
            dfs2(tx, ty);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> str[i][j];
        }
    }
    for (int i = 0; i <= n + 1; i++)
    {
        str[i][0] = '0';
        str[i][m + 1] = '0';
    }
    for (int j = 0; j <= m + 1; j++)
    {
        str[0][j] = '0';
        str[n + 1][j] = '0';
    }
    int flag = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (str[i][j] == '0')
            {
                dfs1(i, j);
                flag = 1;
                break;
            }
        }
        if (flag == 1)
            break;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (str[i][j] == '0')
            {
                cnt++;
                dfs2(i, j);
            }
        }
    }
    cout << cnt;
    return 0;
}