RT,调了一年,后来把数组开到10过了
这份代码为什么会错 2 个大数据点???难道有 5*8 的数据吗??
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1<<8,mod = 12345678;
char s[5][8];
int n,m,px[31],py[31];
ll dp[N][31],ans;
bool vis[10][10];
int dx[9] = {0,1,0,-1,0,1,1,-1,-1};
int dy[9] = {0,0,1,0,-1,1,-1,1,-1};
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
void print_map()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) printf("%c",s[i][j]);
printf("\n");
}
}
int calc()//按照当前状态算出方案数
{
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='X') px[++cnt]=i,py[cnt]=j;
//print_map();
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int mask=0;mask<(1<<cnt);mask++)//枚举状态
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=cnt;i++)//标记当前状态下哪些点不能选
if(!(mask&(1<<(i-1))))//每个最小点周围的点都不能选
for(int j=0;j<=8;j++)
vis[px[i]+dx[j]][py[i]+dy[j]]=1;
int tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) tot+=!vis[i][j];//计算有多少个能选的点
//printf("tot=%d\n",tot);
for(int i=0;i<=tot;i++) //刷表法,i从0开始
if(dp[mask][i])
{
(dp[mask][i+1]+=dp[mask][i]*(tot-i))%=mod;//当前数字不放在最小点
for(int j=0;j<cnt;j++)
if(!(mask&(1<<j)))
(dp[mask|(1<<j)][i+1]+=dp[mask][i])%=mod;//当前数字放在最小点
}
}
//printf("dp:%d\n",dp[(1<<cnt)-1][n*m]);
return dp[(1<<cnt)-1][n*m];
}
void dfs(int x,int y,int op)//op是容斥的正负号
{//dfs从左上向右下一个个填新的状态
if(x==n+1) {ans=(ans+op*calc()%mod+mod)%mod;return;}
if(y==m+1) {dfs(x+1,1,op);return;}
dfs(x,y+1,op);//不改当前这个点的类型
bool flag=1;
for(int i=0;i<=8;i++)
{//判断是否能改当前这个点的类型
int tx=x+dx[i],ty=y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&s[tx][ty]=='X') flag=0;
}
if(flag)
{
s[x][y]='X';
dfs(x,y+1,-op);//改当前这个点的类型
s[x][y]='.';
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='X')
for(int k=1;k<=8;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]=='X')
return puts("0"),0;//特判初始状态不合法
}
dfs(1,1,1);
printf("%lld\n",(ans+mod)%mod);
return 0;
}