P9237 [蓝桥杯 2023 省 A] 像素放置 题解

· · 题解

题意

搜雷，方案唯一。

思路

直接记搜即可。

把当前搜到的坐标 (i,j) 和其上方的两行加两个格子的状态状压起来。

枚举决策 (i,j) 位置填 0 还是 1，然后判断是否满足 (i-1,j-1) 处的限制，就是把周围九个格子 popcount 加一下。

特别地，对于最后一行和最后一列，还要跑 (i-1,j),(i,j-1),(i,j) 的限制，周围六个或四个格子 popcount 加一下。

复杂度 \mathcal O(n^2\times 4^n)。

code

#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);
}