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