| 记录编号 |
287882 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2010冲刺七]翻转游戏 |
最终得分 |
100 |
| 用户昵称 |
 安呐一条小咸鱼。 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.004 s |
| 提交时间 |
2016-08-02 15:30:56 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
char map[6][6];
int h[6][6],a[6][6],tot;
void Change(int x,int y)
{
h[x][y]=!h[x][y];
if(x>=1&&y-1>=1)h[x][y-1]=!h[x][y-1];
if(x-1>=1&&y>=1)h[x-1][y]=!h[x-1][y];
if(x+1<=4&&y<=4)h[x+1][y]=!h[x+1][y];
if(x<=4&&y+1<=4)h[x][y+1]=!h[x][y+1];
}
void open(int *a)
{
}
void Clean()
{
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
h[i][j]=a[i][j];
}
}
}
bool judge()
{
int cnt=0;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
if(h[i][j]==1)cnt++;
}
}
if(cnt==16||cnt==0)return true;
else return false;
}
int Work2(int,int);
int Work1(int a)
{
int ret=0,ans=99999999;
Clean();
for(int i=1;i<=14;i++)
{
if(i==1)
{
ret=0;
Change(1,1),ret++,ret+=Work2(a,0);
if(ret>=99999999)ret=99999999;
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==2)
{
ret=0;
Change(1,2),ret++,ret+=Work2(a,0);
if(ret>=99999999)ret=99999999;
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==3)
{
ret=0;
Change(1,3),ret++,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==4)
{
ret=0;
Change(1,4),ret++,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==5)
{
ret=0;
Change(1,1),Change(1,2),ret+=2,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==6)
{
ret=0;
Change(1,1),Change(1,3),ret+=2,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==7)
{
ret=0;
Change(1,1),Change(1,4),ret+=2,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==8)
{
ret=0;
Change(1,2),Change(1,3),ret+=2,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==9)
{
ret=0;
Change(1,2),Change(1,4),ret+=2,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==10)
{
ret=0;
Change(1,3),Change(1,4),ret+=2,ret+=Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==11)
{
ret=0;
Change(1,1),Change(1,2),Change(1,3),ret+=3+Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==12)
{
ret=0;
Change(1,1),Change(1,2),Change(1,4),ret+=3+Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==13)
{
ret=0;
Change(1,2),Change(1,3),Change(1,4),ret+=3+Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
if(i==14)
{
ret=0;
Change(1,1),Change(1,2),Change(1,3),Change(1,4),ret+=4+Work2(a,0);
ans=min(ret,ans);
// cout<<ret<<endl;
}Clean();
}
if(ans>=99999999)return 99999999;
else return ans;
}
int Work2(int a,int w)
{
int ret=0;
if(w==1)Clean();
for(int i=1;i<=4;i++)
{
if(h[1][i]!=a)
{
Change(2,i);ret++;
}
}
for(int i=1;i<=4;i++)
{
if(h[2][i]!=a)
{
Change(3,i);ret++;
}
}
for(int i=1;i<=4;i++)
{
if(h[3][i]!=a)
{
Change(4,i);ret++;
}
}
if(judge())
{
return ret;
}
return 99999999;
}
int main()
{
freopen("flip.in","r",stdin);freopen("flip.out","w",stdout);
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++){
cin>>map[i][j];
if(map[i][j]=='w')tot++,a[i][j]=1;
if(map[i][j]=='b')a[i][j]=0;
}
}
if(tot==16||tot==0)
{
puts("0");return 0;
}
int a1=Work1(0);
int a2=Work1(1);
int a3=Work2(0,1);
int a4=Work2(1,1);
// cout<<a1<<" "<<a2<<endl;
int ans=min(min(min(a1,a2),a3),a4);
if(ans==99999999)puts("Impossible");
else cout<<ans;
}
/*
bwwb
bbwb
bbwb
bwww
wwww
bwww
bbww
bwww 1
*/