自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:46:39，当前版本为作者最后更新于2023-04-27 00:28:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

搜雷，方案唯一。

思路

直接记搜即可。

把当前搜到的坐标 $(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);
}