UESTC_冬马党 CDOJ 882

时间:2023-03-08 16:34:01

冬马党

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

终于到了冬马党与雪菜党决战的时候了,为了方便,他们的决战之地可看成一个n×m矩阵。

决战前夜,冬马党安插在雪菜党中的内线告诉白学家Kuros,雪菜党已经在他们的决战之地埋下了地雷。

白学家Kuros根据多年来扫雷的经验,推测出雪菜党一定不会在相邻的格子里都放地雷。(两个格子相邻指它们共享一条边)并且,根据先遣部队的探查,某些格子的土地非常坚硬,是不可能埋地雷的。

为了冬马党最终的胜利,Kuros想知道,雪菜党总共有多少种方案来放地雷。

Input

输入第一行为两个整数n,m,表示决战之地的大小。(1≤n≤12,1≤m≤12)

接下来n行,每行m个数,0表示该土地不能放地雷,1表示该土地可以埋地雷。

Output

一行,一个整数,表示总的方案数,答案取100000000的余数。

Sample input and output

Sample Input Sample Output
2 3
1 1 1
0 1 0
9

Source

2014 UESTC Training for Dynamic Programming
解题报告
f(i,j) 表示第i行摆放情况为j的方案数.
用一个dfs进行转移.注意情况:
1.上一行的这个位置已经放了地雷,那么这一行的这里肯定不能再放
2.题目明确禁止这行的这个位置不允许放地雷.
因为我的dfs没有检查同一行两枚地雷相同的情况(非法),所以转移的时候j必须合法,最后答案计数的时候j也必须合法.
最重要的是。。。不要爆了long long(我挂了两发。。)
代码用了滚动数组进行优化~
 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll mod = ;
ll f[][ << ];
bool g[][];
int n,m,r,cur=; void dfs(int pos,int val,ll add)
{
if (pos == -)
f[cur][val] = (f[cur][val] + add) % mod;
else
{
if (val >> pos & || !g[r][pos]) //上一行的这个位置已经放了地雷 / 这个地方不允许放地雷
dfs(pos-,val & ~( << pos),add);
else
{
dfs(pos-,val | ( << pos),add);
dfs(pos-,val,add);
}
}
} bool check(int x)
{
int pre = ;
for(int i = ; i < m ; ++ i)
{
int newx = x >> i & ;
if (newx && pre)
return false;
pre = newx;
}
return true;
} int main(int argc,char *argv[])
{
memset(g,true,sizeof(g));
memset(f,,sizeof(f));
scanf("%d%d",&n,&m);
for(int i = ; i < n ; ++ i)
for(int j = ; j < m ; ++ j)
{
int temp;
scanf("%d",&temp);
if (!temp)
g[i][j] = false;
}
r = ;
dfs(m-, , );
for(int i = ; i < n ; ++ i)
{
cur ^= ;
r = i;
for(int j = ; j < ( << m) ; ++ j) f[cur][j] = ;
for(int j = ; j < ( << m) ; ++ j)
if (check(j))
dfs(m-,j,f[cur^][j]);
}
int ans = ;
for(int i = ; i < ( << m) ; ++ i)
if (check(i))
ans = (ans + f[cur][i]) % mod;
printf("%lld\n",ans % mod);
return ;
}