P4961 小埋与扫雷

标记一下空格和数字，然后遍历整个数组，顺便深搜，求出满足条件的数字个数加上空格连通块个数

#include<iostream>
using namespace std;

const int N = 1010;

#define block 1
#define num 2

int g[N][N];
int st[N][N];
int vis[N][N];
int n, m;

void dfs(int a, int b){
    vis[a][b] = 1;
    for(int i = -1; i <= 1; i ++)
        for(int j = -1; j <= 1; j ++)
            if(i || j){
                int x = a + i, y = b + j;
                if(x >= 0 && x < n && y >= 0 && y < m){
                    if(vis[x][y]) continue;
                    if(st[x][y] != block) continue;
                    dfs(x, y);
                }
            }
}

int main(){
    cin >> n >> m;
    
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> g[i][j];
            
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++){
            if(g[i][j]) continue;
            int flag = 0;
            for(int u = -1; u <= 1; u ++)
                for(int v = -1; v <= 1; v ++)
                    if(u || v) 
                        if(i + u >= 0 && i + u < n && j + v >= 0 && j + v < m)
                            flag |= (g[i + u][j + v] == 1);
            if(flag) st[i][j] = num;
            else st[i][j] = block;
        }
    
    int cnt = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++){
            if(st[i][j] == num){
                int flag = 1;
                for(int u = -1; u <= 1; u ++)
                    for(int v = -1; v <= 1; v ++)
                        if(i + u >= 0 && i + u < n && j + v >= 0 && j + v < m)
                            flag &= (st[i + u][j + v] != block);
                if(flag) cnt ++;
            }
            
            if(st[i][j] == block && !vis[i][j]){
                dfs(i, j);
                cnt ++;
            }
        }
                    
    cout << cnt << endl;
    
    return 0;
}