题目描述

blablabla

样例

6 8
1__5_1
1_4__42_
3__6__5_
56
_6884
6

(dfs) $O(不知道多少)$

第一个剪枝是bfs序剪枝，因为bfs序的相邻的点相关性高，能更好的配合dfs中的剪枝
第二个剪枝（我认为最重要的） 就是当一个区域的白点或者黑点已经到达限制了，那么说明当前在搜索的点一定是黑（白）点

edge存储bfs序列，answer存储答案，mp存储这个点有没有数字（有数字就要是1，为了搭配a数组使用，a数组存储的是该数字，如果这个位置没有数字，就是默认值0）
check数组表示这个位置和周围八个点的黑棋个数

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 10;
int a[N][N];
bool mp[N][N];
bool used[N][N];
int check[N][N];
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1, 0}, dy[] = {-1, 0, 1, 1, -1, -1, 0, 1, 0};
int n, m;
int cnt;
int answer[N][N];
struct EDGE{
    int x, y;
}edge[N];
int res;
void bfs(int a, int b){
    queue<EDGE> q;
    q.push({a, b});
    used[a][b] = 1;

    while(q.size())
    {
        EDGE t = q.front();
        q.pop();
        edge[++ cnt] = {t.x, t.y};
        for(int i = 0; i < 8; i ++){
            int xx = dx[i] + t.x, yy = dy[i] + t.y;
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            if(used[xx][yy]) continue;
            used[xx][yy] = 1;
            q.push({xx, yy});
        }
    }
}
void dfs(int u, int ans)
{
    if(ans == res)
    {
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                cout << answer[i][j];
            }
            cout << endl;
        }
        exit(0);
    }
    if(u == cnt + 1) return ;
    int x = edge[u].x, y = edge[u].y;
    bool flag = 1, flag1 = 1;
    for(int i = 0; i < 9; i ++){
        int xx = x + dx[i], yy = y + dy[i];
        if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
        if(!mp[xx][yy]) continue;
        if(a[xx][yy] == 0){
            flag = 0;
        }
        if(9 - check[xx][yy] ==  a[xx][yy]) flag1 = 0;
        if(!flag && !flag1) break;
    }
    if(flag)
    {
        answer[x][y] = 1;
        for(int i = 0; i < 9; i ++){
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            if(!mp[xx][yy]) continue;
            a[xx][yy] --;
            if(a[xx][yy] == 0) ans ++;
            check[xx][yy] ++;
        }
        dfs(u + 1, ans);    
        for(int i = 0; i < 9; i ++){
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            if(!mp[xx][yy]) continue;
            if(a[xx][yy] == 0) ans --;
            a[xx][yy] ++;
            check[xx][yy] --;
        }
        answer[x][y] = 0;
    }

    if(flag1)
    {
        for(int i = 0; i < 9; i ++){
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            if(!mp[xx][yy]) continue;
            check[xx][yy] ++;
        }
        dfs(u + 1, ans);    
        for(int i = 0; i < 9; i ++){
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            if(!mp[xx][yy]) continue;
            check[xx][yy] --;
        }   
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++){
            char c;
            cin >> c;

            if(c == '_') 
            {
                mp[i][j] = 0;
            }else{
                mp[i][j] = 1;
                a[i][j] = c - '0';
                if(c != '0') res ++;
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m;j ++){
            if(!used[i][j])bfs(i, j);
        }
    }
    memset(used, 0, sizeof used);
    dfs(1, 0);
    return 0;
}