| 记录编号 |
421921 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[UVa 10572] 黑和白 |
最终得分 |
100 |
| 用户昵称 |
 FoolMike |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.280 s |
| 提交时间 |
2017-07-08 14:52:22 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
int n,m;
char str[11][11];
struct state{
int fa[11],size[11],S;
int ok_black,ok_white;
//fa为最小表示,S表示这些位的颜色,1为黑色
state(ll x=0){
memset(fa,0,sizeof fa);
memset(size,0,sizeof size);
ok_black=x>>50&1;
ok_white=x>>60&1;
for (int i=0;i<m;i++) fa[i]=x&7,x>>=3;
for (int i=0;i<m;i++) size[fa[i]]++;
S=x&((1<<(m+1))-1);
}
int get(int p){return S>>p&1;}
bool white(int i,int j){//检查这个格子涂白色是否合法
if (!ok_white) return 0;//白格子已经不联通了
if (i&&j&&!get(j-1)&&!get(j)&&!get(j+1)) return 0;//形成了2*2全白网格
if (i&&get(j+1)&&size[fa[j]]==1){
if (ok_black) ok_black=0;//上面的黑格子不联通
else return 0;
}
if (i&&get(j+1)){//若上面是黑格子,重构这个联通块
int last,set=fa[j];
for (int i=0;i<m;i++)
if (i!=j&&fa[i]==set){last=i;break;}
for (int i=0;i<m;i++)
if (i!=j&&fa[i]==set) fa[i]=last;
}
int set=j;
if (j&&!get(j-1)) set=min(set,fa[j-1]);//左边是白格子
if (i&&!get(j+1)) set=min(set,fa[j]);//上面是白格子
if (j&&!get(j-1)){//合并左边的联通块
int s=fa[j-1];
for (int i=0;i<m;i++)
if (fa[i]==s) fa[i]=set;
}
if (i&&!get(j+1)){//合并上边的联通块
int s=fa[j];
for (int i=0;i<m;i++)
if (fa[i]==s) fa[i]=set;
}
fa[j]=set;
S&=~(1<<j);//将这一位颜色染白
return 1;
}
bool black(int i,int j){
if (!ok_black) return 0;//黑格子已经不联通了
if (i&&j&&get(j-1)&&get(j)&&get(j+1)) return 0;//形成了2*2全黑网格
if (i&&!get(j+1)&&size[fa[j]]==1){
if (ok_white) ok_white=0;
else return 0;//上面的白格子不联通
}
if (i&&!get(j+1)){//若上面是白格子,重构这个联通块
int last,set=fa[j];
for (int i=0;i<m;i++)
if (i!=j&&fa[i]==set){last=i;break;}
for (int i=0;i<m;i++)
if (i!=j&&fa[i]==set) fa[i]=last;
}
int set=j;
if (j&&get(j-1)) set=min(set,fa[j-1]);//左边是黑格子
if (i&&get(j+1)) set=min(set,fa[j]);//上面是黑格子
if (j&&get(j-1)){//合并左边的联通块
int s=fa[j-1];
for (int i=0;i<m;i++)
if (fa[i]==s) fa[i]=set;
}
if (i&&get(j+1)){//合并上边的联通块
int s=fa[j];
for (int i=0;i<m;i++)
if (fa[i]==s) fa[i]=set;
}
fa[j]=set;
S|=(1<<j);//将这一位颜色染黑
return 1;
}
bool ok(){
int block=0;
for (int i=0;i<m;i++)
if (fa[i]==i) block++;
if (block>2) return 0;
int is_black=0,is_white=0;
for (int i=1;i<=m;i++)
if (get(i)) is_black=1;
else is_white=1;
if (is_black&&!ok_black) return 0;
if (is_white&&!ok_white) return 0;
return 1;
}
ll val(){
ll x=S;
for (int i=m-1;i>=0;i--) x=x<<3|fa[i];
x|=((ll)ok_black<<50);
x|=((ll)ok_white<<60);
return x;
}
void print(){
puts("this is fa array:");
for (int i=0;i<m;i++) printf("%d ",fa[i]);
puts("");
puts("this is the color set");
for (int i=0;i<=m;i++) printf("%d",S>>i&1);
puts("");
printf("black:%d\n",ok_black);
printf("white:%d\n",ok_white);
puts("state end.");
puts("");
}
};
typedef pair<ll,ll> pr;
struct dp_array{
vector<pr> v;//first为状态,second为出现次数
map<ll,ll> M;
void clear(){
v.clear();
M.clear();
}
void add(ll S,ll d){//状态S的出现次数+d
if (!M.count(S)) M[S]=v.size(),v.push_back(pr(S,d));
else v[M[S]].second+=d;
}
}*x=new dp_array(),*y=new dp_array();
void solve(int i,int j){
y->clear();
for (int k=0;k<x->v.size();k++){
state S(x->v[k].first),T;
ll v=x->v[k].second;
if (str[i][j]!='#'){
T=S;
if (T.white(i,j)) y->add(T.val(),v);
}
if (str[i][j]!='o'){
T=S;
if (T.black(i,j)) y->add(T.val(),v);
}
}
swap(x,y);
}
void next_line(int i){
y->clear();
for (int k=0;k<x->v.size();k++){
state S(x->v[k].first);
S.S&=~(1<<m);
S.S<<=1;
y->add(S.val(),x->v[k].second);
}
swap(x,y);
}
int main()
{
freopen("blackandwhite.in","r",stdin);
freopen("blackandwhite.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) scanf("%s",str[i]);
x->add((1ll<<50)|(1ll<<60),1);
for (int i=0;i<n;next_line(i),i++)
for (int j=0;j<m;solve(i,j),j++);
ll ans=0;
for (int i=0;i<x->v.size();i++){
state S(x->v[i].first);
if (S.ok()) ans+=x->v[i].second;
}
printf("%lld\n",ans);
return 0;
}