L2-048 寻宝图

思路

• 判断连通块的个数，直接用dfs(), 把连通块全部标记为访问过，枚举从某个点出发
• 坑点，如果我们从宝藏的进入dfs()，宝藏应该提前判断

#include <bits/stdc++.h>
//#define int long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
string g[N];
string st[N];
int n, m, ff;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void dfs(int x, int y)
{
    for(int i = 0; i < 4; i ++)
    {
        int nex = x + dx[i], ney = y + dy[i];
        if(nex < 0 || nex >= n || ney < 0 || ney >= m) continue;
        if(g[nex][ney] == '0' || st[nex][ney] == '1') continue;
        st[nex][ney] = '1';
        if(g[nex][ney] > '1') ff = 1;
        dfs(nex, ney);
    }
}
signed main()
{
    int res = 0, ans = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++) st[i] += '0';
    }
    for(int i = 0; i < n; i ++)
    {
        cin >> g[i];
    }

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(st[i][j] == '1' || g[i][j] == '0' ) continue;
            ff = 0;
            if(g[i][j] > '1') ff = 1;
            dfs(i, j);
            res ++; // 岛屿个数
            if(ff) ans ++; // 保藏个数
        }
    }
    cout << res << ' ' << ans << endl;
    return 0;
}