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 |
贴个AC代码#include<iostream> using namespace std; int chess[17]; int k; int judge() { int i; for(i=2;i<=16;i++) if(chess[i]!=chess[i-1]) return 0; return 1; } void convert(int i) { chess[i]^=1; if(i%4!=1) chess[i-1]^=1; if(i%4!=0) chess[i+1]^=1; if(i>4) chess[i-4]^=1; if(i<13) chess[i+4]^=1; } void dfs(int j,int now,int total)//现在到第j个棋子了,翻转了now次,总共翻转了total次。 { int i; if(now==total) { k=judge(); return; } for(i=j+1;i<=16;i++) { convert(i); dfs(i,now+1,total); if(k) return; convert(i);//还原。 } } int main() { int i; char ch; for(i=1;i<=16;i++)//输入,用0代替w,用1代替b。 { cin>>ch; if(ch=='w') chess[i]=0; else chess[i]=1; } k=judge(); if(k) cout<<0<<endl; else { for(i=1;i<=16;i++)//最多翻转16次,枚举。 { k=0; dfs(0,0,i); if(k) break; } if(k) cout<<i<<endl; else cout<<"Impossible\n"; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator