| 记录编号 |
596823 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[UVa 10572] 黑和白 |
最终得分 |
100 |
| 用户昵称 |
 flyfree |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.260 s |
| 提交时间 |
2024-11-08 16:13:52 |
内存使用 |
164.57 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100010
#define mod 29987
#define lst now-1
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll dp[70][MAXN],que[70][MAXN],frm[70][MAXN],cnt[70];
ll s[10][10],pre[15],ans_c[10][10],_col[20];
ll hd[30010],nxt[MAXN];
ll T,n,m,now,wx,wy,bx,by,k,sum_ans;
char c;
void insert(ll sta,ll val,ll fr){
ll u=sta%mod;
for(int i=hd[u];i;i=nxt[i]){
if(que[now][i]==sta){
dp[now][i]+=val;
return;
}
}
nxt[++cnt[now]]=hd[u];
hd[u]=cnt[now];
dp[now][cnt[now]]=val;
que[now][cnt[now]]=sta;
frm[now][cnt[now]]=fr;
}
ll work(ll sta){
ll idxw=2,idxb=1,y=0;
memset(_col,0,sizeof(_col));
for(int i=1;i<=m;i++){
ll col=(sta>>(i-1)*4)%16;
if(!col)continue;
if(!_col[col]){
if(col%2==1)_col[col]=idxb,idxb+=2;
else _col[col]=idxw,idxw+=2;
}
y+=_col[col]*pre[i];
}
return y;
}
void write(ll sta){
if((sta>>m*4)%16==1)cout<<"Black ";
else if((sta>>m*4)%16==2)cout<<"White ";
else cout<<"Empty ";
// cout<<(sta>>m*4)%16<<" ";
for(int i=1;i<=m;i++){
cout<<(sta>>(i-1)*4)%16<<" ";
}
// cout<<endl;
}
ll pd(ll x,ll y,ll sta,ll col){
if((x<n&&y<m)||x<n-1)return 0;
if((sta>>m*4)%2==col&&(sta>>(y-1)*4)%2==col&&(y>1&&(sta>>(y-2)*4)%2==col))return 0;
ll re_ans=0;
for(int i=1;i<=m;i++){
ll col_now=(sta>>(i-1)*4)%16;
if(col_now%2!=col)re_ans=max(re_ans,col_now);
}
if(re_ans>2)return 0;
if(x==n){
for(int i=y+1;i<=m;i++){
ll col_now=(sta>>((i-1)*4))%2,col_lst=(sta>>((i-2)*4))%2;
if(col_now==col_lst&&col_now==col)return 0;
}
return 1;
}else{
for(int i=2;i<=m;i++){
ll col_now=i==m?col:(sta>>((i-1)*4))%2,col_lst=(sta>>((i-2)*4))%2;
if(col_now==col_lst&&col_now==col)return 0;
}
return 1;
}
}
ll re_max(ll sta){
ll re_ans=0;
for(int i=1;i<=m;i++){
re_ans=max(re_ans,(sta>>(i-1)*4)%16);
}
return re_ans;
}
void clear(){
memset(dp,0,sizeof(dp));
memset(que,0,sizeof(que));
memset(cnt,0,sizeof(cnt));
memset(frm,0,sizeof(frm));
memset(ans_c,0,sizeof(ans_c));
memset(hd,0,sizeof(hd));
memset(nxt,0,sizeof(nxt));
k=0;
wx=0,wy=0,bx=0,by=0,now=0,sum_ans=0;
}
void clear_ans(ll x,ll y,ll i,ll col){
ll qwe=lst;
ll h=i;
for(int u=y-1;u;u--){
if((que[qwe][h]>>(u-1)*4)%2)ans_c[x][u]=1;
else ans_c[x][u]=2;
h=frm[qwe][h];
qwe--;
}
for(int j=x-1;j;j--){
for(int u=m;u;u--){
if((que[qwe][h]>>(u-1)*4)%2)ans_c[j][u]=1;
else ans_c[j][u]=2;
h=frm[qwe][h];
qwe--;
}
}
k=1;
if(x!=n||y!=m){
for(int j=y;j<=m;j++)ans_c[x][j]=col;
for(int j=1;j<=m;j++)ans_c[n][j]=col;
}
}
int main(){
freopen("blackandwhite.in","r",stdin);
freopen("blackandwhite.out","w",stdout);
// cin>>T;
T=1;
pre[1]=1;
for(int i=2;i<=10;i++)pre[i]=pre[i-1]<<4;
while(T--){
clear();
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='.')s[i][j]=0;
else if(c=='#')s[i][j]=1,bx=i,by=j;
else s[i][j]=2,wx=i,wy=j;
}
}
que[0][++cnt[now]]=0;
dp[0][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt[now];j++)que[now][j]%=pre[m+1];
for(int j=1;j<=m;j++){
now++;
memset(hd,0,sizeof(hd));
memset(nxt,0,sizeof(nxt));
// cout<<"\n-------------\n";
// cout<<i<<" "<<j<<endl;
for(int u=1;u<=cnt[lst];u++){
ll g=0,p_up=(que[lst][u]>>(j-1)*4)%16,p_rht=j>1?(que[lst][u]>>(j-2)*4)%16:0,_p=(que[lst][u]>>m*4)%16;
// write(que[lst][u]);
for(int sz=1;sz<=m;sz++){
if((que[lst][u]>>(sz-1)*4)%16==p_up&&sz!=j)g=1;
}
// cout<<"val: "<<dp[lst][u]<<endl;
if(s[i][j]!=2&&((p_up==0||p_up%2==0)||(p_rht==0||p_rht%2==0)||(_p%2==0||_p==0))){//染成黑格
if(!g&&p_up%2==0&&p_up!=0){
// if((i>wx||(i>=wx&&j>wy))&&!k)
if((i>wx||(i>=wx&&j>wy))&&pd(i,j,que[lst][u],1)){
sum_ans+=dp[lst][u];
if(!k)clear_ans(i,j,u,1);
// cout<<"UNO! Black\n";
}
}else{
ll y=que[lst][u];
for(int sz=1;sz<=m;sz++){
ll col=(que[lst][u]>>(sz-1)*4)%16;
if(((col%2==1&&col==p_up)||(col%2==1&&col==p_rht))&&col!=0&&sz!=j){
y=y-col*pre[sz]+pre[sz]*15;
}
}
y=y-p_up*pre[j]+15*pre[j];
// cout<<y<<endl;
y=work(y);
y=y%pre[m+1]+(p_up%2==0?(p_up==0?0:2):1)*pre[m+1];
// cout<<"To: ";
// write(y);
// cout<<endl;
insert(y,dp[lst][u],u);
}
}
if(s[i][j]!=1&&((p_up==0||p_up%2==1)||(p_rht==0||p_rht%2==1)||(_p==0||_p%2==1))){//染成白格
if(!g&&p_up%2==1&&p_up!=0){
if((i>bx||(i>=bx&&j>by))&&pd(i,j,que[lst][u],0)){
sum_ans+=dp[lst][u];
if(!k)clear_ans(i,j,u,2);
// cout<<"UNO! White\n";
}
}else{
ll y=que[lst][u];
for(int sz=1;sz<=m;sz++){
ll col=(que[lst][u]>>(sz-1)*4)%16;
if(((col%2==0&&col==p_up)||(col%2==0&&col==p_rht))&&col!=0&&sz!=j){
y=y-col*pre[sz]+pre[sz]*14;
}
}
y=y-p_up*pre[j]+14*pre[j];
// cout<<y<<" ";
y=work(y);
// cout<<"To: ";
y=y%pre[m+1]+(p_up%2==0?(p_up==0?0:2):1)*pre[m+1];
// write(y);
// cout<<endl;
// cout<<y<<endl;
insert(y,dp[lst][u],u);
}
}
}
}
}
now++;
for(int i=1;i<=cnt[lst];i++){
// cout<<"\n-------\n";
// write(que[lst][i]);
// cout<<re_max(que[lst][i])<<endl;
if(re_max(que[lst][i])>2)continue;
sum_ans+=dp[lst][i];
if(!k){
clear_ans(n,m,i,0);
}
}
cout<<sum_ans<<endl;
// if(sum_ans==0)continue;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// if(ans_c[i][j]==1)cout<<'#';
// else cout<<'o';
// }
// cout<<endl;
// }
}
return 0;
}