| ||||||||||
| 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 | |||||||||
Re:DFS AC代码In Reply To:DFS AC代码 Posted by:452181625 at 2014-05-13 21:25:52 > #include<iostream>
> using namespace std;
> int handle[5][5],ways[17][2];
> int k,l;
> int judge()
> {
> int i,j,sum=0;
> for(i=1;i<=4;i++)
> for(j=1;j<=4;j++)
> sum+=handle[i][j];
> if(sum==16) return 1;
> return 0;
> }
> void convert(int i,int j)
> {
> int kk;
> handle[i][j]^=1;
> for(kk=1;kk<=4;kk++)
> {
> handle[i][kk]^=1;
> handle[kk][j]^=1;
> }
> }
> void dfs(int ii,int jj,int now,int total,int ll)//现在到ii,jj开关了,翻转了now次,总共翻转了total次。
> {
> int i,j;
> if(now==total)
> {
> k=judge();
> l=ll;
> return;
> }
> for(i=ii;i<=4;i++)//注意转换,行不变,第一次jj向后移一位,以后从1开始。
> {
> if(i==ii) j=jj+1;
> else j=1;
> for(;j<=4;j++)
> {
> ways[ll][0]=i;
> ways[ll][1]=j;
> convert(i,j);
> dfs(i,j,now+1,total,ll+1);
> if(k) return;
> convert(i,j);//还原。
> }
> }
> }
> int main()
> {
> int i,j;
> char ch;
> for(i=1;i<=4;i++)//输入,用0代替w,用1代替b。
> for(j=1;j<=4;j++)
> {
> cin>>ch;
> if(ch=='+') handle[i][j]=0;
> else handle[i][j]=1;
> }
> cout<<endl;
> for(i=1;i<=16;i++)//最多翻转16次,枚举。
> {
> k=0;
> dfs(1,0,0,i,1);//起点(1,0)
> if(k) break;
> }
> cout<<i<<endl;
> for(i=1;i<=l-1;i++)
> cout<<ways[i][0]<<' '<<ways[i][1]<<endl;
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator