68. 像素放置

#include<stdio.h>
#include<bitset>
#define ppc __builtin_popcount
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,ans[11][11];bitset<1024>v[10][10][4][1024];char s[11][11];
inline void dfs(int i,int j,int s1,const int&s2,
    const int&s3)
{
    if(j==m)++i,j=0,s1=0;
    if(i==n)
    {
        for(int i=0;i<n;++i,putchar('\n'))
            for(int j=0;j<m;printf("%d",ans[i][j++]));
        exit(0);
    }
    if(v[i][j][s1][s2][s3])return;
    v[i][j][s1][s2][s3]=1;
    ans[i][j]=1;//(i,j)填1
    if(i&&j&&(s[i-1][j-1]^'_'))if(s[i-1][j-1]^'0'^ppc(s1)+
        ppc(s2>>m-j-1&7)+ppc(s3>>m-j-1&7)+1)goto qwq;
    if(i&&j==m-1&&(s[i-1][j]^'_'))if(s[i-1][j]^'0'^(s1&1)+ppc(s2&3)+
        ppc(s3&3)+1)goto qwq;
    if(i==n-1&&j&&(s[i][j-1]^'_'))if(s[i][j-1]^'0'^ppc(s2>>m-j&3)+
        ppc(s3>>m-j-1&7)+1)goto qwq;
    if(i==n-1&&j==m-1&&(s[i][j]^'_'))if(s[i][j]^'0'^(s2>>1&1)+(s3>>1&1)
        +(s3&1)+1)goto qwq;
    dfs(i,j+1,(s1&1)<<1|(s2>>m-j-1&1),(s2&~(1<<m-j-1))|(s3>>m-j-1&1)<<m-j-1,
        (s3&~(1<<m-j-1))|1<<m-j-1);
    qwq:ans[i][j]=0;//(i,j)填0
    if(i&&j&&(s[i-1][j-1]^'_'))if(s[i-1][j-1]^'0'^ppc(s1)+ppc(s2>>m-j-1&7)+
        ppc(s3>>m-j-1&7))goto pwp;
    if(i&&j==m-1&&(s[i-1][j]^'_'))if(s[i-1][j]^'0'^(s1&1)+ppc(s2&3)+ppc(s3&3))
        goto pwp;
    if(i==n-1&&j&&(s[i][j-1]^'_'))if(s[i][j-1]^'0'^ppc(s2>>m-j&3)+
        ppc(s3>>m-j-1&7))goto pwp;
    if(i==n-1&&j==m-1&&(s[i][j]^'_'))if(s[i][j]^'0'^(s2>>1&1)+(s3>>1&1)
        +(s3&1))goto pwp;
    dfs(i,j+1,(s1&1)<<1|(s2>>m-j-1&1),(s2&~(1<<m-j-1))|(s3>>m-j-1&1)<<m-j-1,
        s3&~(1<<m-j-1));
    pwp:;
}
main()
{
    read(n);read(m);
    for(int i=0;i<n;++i)for(int j=0;j<m;++j)
        for(;s[i][j]=nc(),(s[i][j]<'0'||'9'<s[i][j])&&(s[i][j]^'_'););
    dfs(0,0,0,0,0);
}

import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        int[][] g = new int[n][m];
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < line.length(); j++) {
                char c = line.charAt(j);
                if (c == '_') continue;
                g[i][j] = c - '0';
            }
        }
        int[] ans = new int[n];
        dfs(ans, g, n - 1);
        for (int x : ans) {
            printInt(x, m);
        }

    }

    static void printInt(int n, int m) {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < m; i++) {
            s.append(n >> i & 1);
        }
        System.out.println(s);
    }

    static boolean dfs(int[] ans, int[][] g, int i) {
        int n = g.length, m = g[0].length;
        // 所有行的状态都枚举完毕且符合，返回true
        if (i < 0) return true;
        // 每一行都重新从0开始枚举状态
        for (ans[i] = 0; ans[i] < (1 << m); ans[i]++) {
            // 如果当前状态满足条件，则往上一行继续枚举
            if (check(ans, g, i) && dfs(ans, g, i - 1)) {
                return true;
            }
        }
        // 如果无法得到正确的排列，需要将此行重置，防止后续dfs时cnt计算错误
        ans[i] = 0;
        return false;
    }

    // 当枚举到第i行时，需要先校验第i行和第i+1行的数字是否满足
    static boolean check(int[] ans, int[][] g, int i) {
        int n = g.length, m = g[0].length;
        for (int j = 0; j < m; j++) {
            // 第i行
            if (g[i][j] > 0) {
                int c = cnt(ans, i, j);
                // 第0行特判，因为没有补救机会了，只能判断是否相等
                if (i == 0 && c != g[i][j]) return false;
                // 由于还有第i-1行没有枚举，所以第i行只判断是否大于（如果小于的话，在i-1行还有补救机会）
                if (i > 0 && c > g[i][j]) return false;
            }
            // 第i+1行
            if (i + 1 < n && g[i + 1][j] > 0) {
                int c = cnt(ans, i + 1, j);
                // 第i+1行的数字已经可以完整判断了，因为i,i+1,i+2这三行都已经枚举了状态
                if (c != g[i + 1][j]) return false;
            }
        }
        return true;
    }

    // 获取第i行第j列周围数字
    static int cnt(int[] ans, int i, int j) {
        int cnt = 0;
        for (int r = i - 1; r <= i + 1; r++) {
            if (r < 0 || r >= ans.length) continue;
            for (int c = j - 1; c <= j + 1; c++) {
                if (c < 0) continue;
                cnt += ans[r] >> c & 1;
            }
        }
        return cnt;
    }
}