晕。。这道题目其实不算太难。当时脑子小了囧。。
只要dp就可以了。实际上由于黑色的最多只有8个,那么状态就是(usedRow,usedCol,LeftRow,LeftCol).其中最后一个没必要储存,是有前三个唯一确定的。。
首先把黑色的全往左上角扔。。那么左上角的“黑块”最多只有8*8大小。
usedRow就是黑块的row的占用情况,usedCol就是黑块的Col占用的情况,LeftRow就剩下的没被占用的白色Row,LeftCol也一样,然后Dp就可以了囧。。最恶心的是如果边界情况就是没有任何后继的话答案应该是1,但不能根据答案是否为0判断,因为它也可能恰好是10000000007的倍数额啊囧。。好吧code太ugly了囧。。
手机买了居然是山寨的晕死。。现在高仿太多了囧。。
Code:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef long long ll;
typedef unsigned long long ull;
class DrawingBlackCrosses {
public:
int count(vector <string>);
};
const int maxn=20;
const ll mod=1000000007;
bool a[maxn][maxn];
int bn,bm,n,m;
ll Dp[maxn+1][1<<8][1<<8];
bool S[maxn+1][1<<8][1<<8]={0};
ll dfs(int ur,int uc,int ln,int lm)
{
ll&x=Dp[ln][ur][uc];
if(S[ln][ur][uc]) return x;
S[ln][ur][uc]=true;x=0;bool ok=false;
rep(i,bn)rep(j,bm)if((ur&(1<<i))==0&&(uc&(1<<j))==0&&!a[i][j])
x+=dfs(ur^(1<<i),uc^(1<<j),ln,lm),x%=mod,ok=true;
if(lm>0)rep(i,bn)if((ur&(1<<i))==0) x+=dfs(ur^(1<<i),uc,ln,lm-1)*lm,x%=mod,ok=true;
if(ln>0)rep(i,bm)if((uc&(1<<i))==0)x+=dfs(ur,uc^(1<<i),ln-1,lm)*ln,x%=mod,ok=true;
if(ln>0&&lm>0)x+=dfs(ur,uc,ln-1,lm-1)*ln*lm,x%=mod,ok=true;
if(!ok)x=1;
return x;
}
int DrawingBlackCrosses::count(vector <string> field) {
vector<string>T(all(field)),A;
sort(all(T));
reverse(all(T));
rep(i,T[0].size())
{
string a="";
rep(j,T.size())
{
a+=T[j][i];
}
A.pb(a);
}
sort(all(A));
reverse(all(A));bn=bm=0;n=A.size();m=A[0].size();
rep(i,n)rep(j,m)
{
a[i][j]=A[i][j]==’B’;
if(a[i][j]) bn>?=i+1,bm>?=j+1;
}
return dfs(0,0,n-bn,m-bm);
}