| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
留给同学的In Reply To:居然WA是因为Impossible 打错,无线汗~~~ Posted by:stupidjohn at 2010-05-26 23:45:47 // POJ 1753
#include<iostream>
using namespace std;
int direction[4][2]={1,0,0,1,0,-1,-1,0};
int bnumber;
char map[4][4];
int clip[16];
int clips;
int isin(int x,int y)
{
return (x>=0&&x<4&&y>=0&&y<4);
}
int min(int a,int b)
{
return a<b?a:b;
}
void work()
{
int i,tclip=0;
for(i=0;i<16;i++)
if(clip[i])
{
tclip++;
}
clips=min(clips,tclip);
}
void change(int x,int y)
{
if(map[x][y]=='b'){map[x][y]='w';bnumber--;return;}
else{map[x][y]='b';bnumber++;}
}
void run(int n)
{
int i,x,y,newx,newy;
if(n>16) return;
if(bnumber==0||bnumber==16) work();
if(n>15) return;
x=n/4;y=n%4;
clip[n]=1;
change(x,y);
for(i=0;i<4;i++)
{
newx=x+direction[i][0];
newy=y+direction[i][1];
if(isin(newx,newy))
{
change(newx,newy);
}
}
run(n+1);
change(x,y);
for(i=0;i<4;i++)
{
newx=x+direction[i][0];
newy=y+direction[i][1];
if(isin(newx,newy))
{
change(newx,newy);
}
}
clip[n]=0;
run(n+1);
}
int main()
{
int i,j;
for(i=0;i<16;i++)
clip[i]=0;
clips=100;
bnumber=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
cin>>map[i][j];
if(map[i][j]=='b') bnumber++;
}
if(bnumber==0||bnumber==16)
cout<<0<<endl;
else
{
run(0);
if(clips==100) cout<<"Impossible"<<endl;
else cout<<clips<<endl;
}
return 1;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator