P2040 打开所有的灯

admin

https://www.luogu.org/problemnew/show/P2040

题目背景
pmshz在玩一个益(ruo)智(zhi)的小游戏，目的是打开九盏灯所有的灯，这样的游戏难倒了pmshz。。。

题目描述
这个灯很奇(fan)怪(ren)，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是告诉pmshz要全部打开这些灯。

例如 0 1 1
1 0 0
1 0 1

点一下最中间的灯【2,2】就变成了

0 0 1
0 1 1
1 1 1

再点一下左上角的灯【1,1】就变成了

1 1 1
1 1 1
1 1 1

达成目标。最少需要2步。

输出2即可。

输入输出格式
输入格式：
九个数字，3*3的格式输入，每两个数字中间只有一个空格，表示灯初始的开关状态。（0表示关，1表示开）

输出格式：
1个整数，表示最少打开所有灯所需要的步数。

输入输出样例
输入样例#1：
0  1  1
1  0  0
1  0  1
输出样例#1：
2
说明
这个题水不水，就看你怎么考虑了。。。。

黄煦喆

1. #include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. int b[5][5];
   
5. struct mp
   
6. {
   
7.     int a[5][5];
   
8.     int step;
   
9. } f[600];
   
10. queue<mp>q;
    
11. int num;
    
12. int tx[5]= {0,+1,-1,+0,+0};
    
13. int ty[5]= {0,+0,+0,-1,+1};
    
14. int main()
    
15. {
    
16.     int ss=0;
    
17.     for(int i=1; i<=3; i++)
    
18.         for(int j=1; j<=3; ++j)
    
19.         {
    
20.             cin>>b[i][j];
    
21.             ss=ss*2+b[i][j];
    
22.         }
    
23.     for(int i=1; i<=3; i++)
    
24.         for(int j=1; j<=3; j++)f[ss].a[i][j]=b[i][j];
    
25.     f[ss].step=0;
    
26.     q.push(f[ss]);
    
27.     while(q.size()&&!f[511].step)
    
28.     {
    
29.         int s=0;
    
30.         mp t=q.front();
    
31.         q.pop();
    
32.         for(int i=1; i<=3; i++)
    
33.             for(int j=1; j<=3; j++)
    
34.                 s=s*2+t.a[i][j];
    
35.         if(!f[s].step)
    
36.         {
    
37.             f[s].step=t.step;
    
38.             for(int i=1; i<=3; i++)
    
39.                 for(int j=1; j<=3; j++)
    
40.                 {
    
41.                     mp l=t;
    
42.                     int x=i,y=j;
    
43.                     l.step++;
    
44.                     for(int i=0; i<=4; i++)
    
45.                     {
    
46.                         int gx=x+tx[i],gy=y+ty[i];
    
47.                         l.a[gx][gy]=1-l.a[gx][gy];
    
48.                     }
    
49.                     q.push(l);
    
50.                 }
    
51.         }
    
52.     }
    
53.     cout<<f[511].step;
    
54.     return 0;
    
55. }
    

复制代码

admin

这个题很值得一做，大家都认真做做！我的程序一向是值得学习的，请看我的

admin

第一种做法，每个开关都可以按1下，按2下及以上是没有意义的，所以枚举每个开关按与不按，穷举9个开关的状态。

admin

第二种做法，dfs，枚举000000000-111111111之间的所有数字，判断

admin

第三种，BFS。每次可以按1号到9号开关，顺序广搜。我这里为了清晰，写的有点麻烦。

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. const int mn=600; ///最多512下
   
5. int x,y;
   
6. int s[mn],d[mn];
   
7. ///step表示到达此状态需要几下
   
8. ///d表示进队列的先后顺序
   
9. int press(int x,int k) ///按动第k个开关 x变成了y
   
10. {
    
11.     int a[10]={0},i=9;
    
12.     ///x化成2进制
    
13.     while (x>0){a[i]=x%2;x=x/2;i--;}
    
14.     ///按动
    
15.     if (k==1) {a[1]=!a[1];a[2]=!a[2];a[4]=!a[4];}
    
16.     if (k==2) {a[1]=!a[1];a[2]=!a[2];a[3]=!a[3];a[5]=!a[5];}
    
17.     if (k==3) {a[2]=!a[2];a[3]=!a[3];a[6]=!a[6];}
    
18.     if (k==4) {a[1]=!a[1];a[4]=!a[4];a[5]=!a[5];a[7]=!a[7];}
    
19.     if (k==5) {a[2]=!a[2];a[4]=!a[4];a[5]=!a[5];a[6]=!a[6];a[8]=!a[8];}
    
20.     if (k==6) {a[3]=!a[3];a[5]=!a[5];a[6]=!a[6];a[9]=!a[9];}
    
21.     if (k==7) {a[4]=!a[4];a[7]=!a[7];a[8]=!a[8];}
    
22.     if (k==8) {a[5]=!a[5];a[7]=!a[7];a[8]=!a[8];a[9]=!a[9];}
    
23.     if (k==9) {a[6]=!a[6];a[8]=!a[8];a[9]=!a[9];}
    
24. 
    
25.     ///拼成数字
    
26.     int y=0;
    
27.     for (i=1;i<=9;i++) y=2*y+a[i];
    
28.     return y;
    
29. }
    
30. 
    
31. int head,tail,temp,t,i;
    
32. bool bb;
    
33. int main()
    
34. {
    
35.     for (i=1;i<=9;i++) {cin>>t; x=2*x+t;}
    
36.     if (x==511) cout<<0;  ///特殊判断
    
37.     else
    
38.     {
    
39.         head=tail=1;
    
40.         d[1]=x;
    
41.         s[x]=1;
    
42.         bb=0;
    
43.         while (tail>=head  &&  tail<=520 && !bb)
    
44.         {
    
45.             temp=d[head];
    
46.             for (i=1;i<=9;i++)
    
47.             {
    
48.                 y=press(temp,i);
    
49.                 bb=y==511;
    
50.                 if (s[y]==0)
    
51.                     {s[y]=s[temp]+1;
    
52.                 tail++;d[tail]=y;
    
53.                 }
    
54.             }
    
55. 
    
56.             head++;
    
57. 
    
58.             /*
    
59.             cout<<"d ";
    
60.             for (i=1; i<=10; i++) cout<<setw(3)<<d[i];
    
61.             cout<<endl;
    
62.             cout<<"s ";
    
63.             for (i=1; i<=10; i++) cout<<setw(3)<<s[i];
    
64.             cout<<endl;
    
65.             */
    
66.         }
    
67. 
    
68.     }
    
69.     cout<<s[511]-1;
    
70.     return 0;
    
71. }
    

复制代码

张笑宇

来一发dfs

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int a[5][5],i,j,ans=9999;
   
5. bool b[5][5];
   
6. bool cmp()
   
7. {
   
8.     for (i=1; i<=3; i++)
   
9.         for (int j=1; j<=3; j++)
   
10.             if (a[i][j]==0) return false;
    
11.     return true;
    
12. }
    
13. void change(int tx,int ty)
    
14. {
    
15.     a[tx-1][ty]=abs(a[tx-1][ty]-1);
    
16.     a[tx+1][ty]=abs(a[tx+1][ty]-1);
    
17.     a[tx][ty-1]=abs(a[tx][ty-1]-1);
    
18.     a[tx][ty+1]=abs(a[tx][ty+1]-1);
    
19.     a[tx][ty]=abs(a[tx][ty]-1);
    
20. }
    
21. void dfs(int x)
    
22. {
    
23.     if (cmp()) ans=min(ans,x);
    
24.     else for (int k=1; k<=3; k++)
    
25.             for (int v=1; v<=3; v++)
    
26.             {
    
27.                 if (b[k][v]==0)///没走过
    
28.                 {
    
29.                     b[k][v]=1;
    
30.                     change(k,v);
    
31.                     dfs(x+1);
    
32.                     change(k,v);
    
33.                     b[k][v]=0;
    
34.                 }
    
35.             }
    
36. }
    
37. int main()
    
38. {
    
39.     for (i=1; i<=3; i++)
    
40.         for (j=1; j<=3; j++) cin>>a[i][j];
    
41.     dfs(0);
    
42.     cout<<ans;
    
43.     return 0;
    
44. }
    

复制代码

张笑宇

请教孙老师：为什么不对？？？

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int mx=5;
   
5. const int mm=10001;///a当前
   
6. int a[mx][mx],d[mm],n[mm];///n步数
   
7. int i,j,k,head,tail;
   
8. bool cmp()
   
9. {
   
10.     for (int ii=1; ii<=3; ii++)
    
11.         for (int jj=1; jj<=3; jj++)
    
12.             if (a[ii][jj]==0) return false;
    
13.     return true;
    
14. }
    
15. void change(int tx,int ty)
    
16. {
    
17.     a[tx-1][ty]=abs(a[tx-1][ty]-1);
    
18.     a[tx+1][ty]=abs(a[tx+1][ty]-1);
    
19.     a[tx][ty-1]=abs(a[tx][ty-1]-1);
    
20.     a[tx][ty+1]=abs(a[tx][ty+1]-1);
    
21.     a[tx][ty]=abs(a[tx][ty]-1);
    
22. }
    
23. int main()
    
24. {
    
25.     for (i=1; i<=3; i++)
    
26.         for (j=1; j<=3; j++) cin>>a[i][j];
    
27.     head=1,tail=1;
    
28.     while (head<=tail)
    
29.     {
    
30.         int temp=d[head];
    
31.         n[temp]++;
    
32.         for (i=1; i<=3; i++)
    
33.             for (j=1; j<=3; j++)
    
34.             {
    
35.                 change(i,j);
    
36.                 if (cmp())
    
37.                 {
    
38.                     cout<<n[temp];
    
39.                     return 0;
    
40.                 }
    
41.                 d[tail]=temp;
    
42.                 tail++;
    
43.                 change(i,j);
    
44.             }
    
45.         head++;
    
46.     }
    
47.     return 0;
    
48. }
    

复制代码

admin

评点下上面两个同学的程序
HXZ的tx ty有很大的隐患，简易tr tc
ZXY的a[tx-1][ty]=abs(a[tx-1][ty]-1); 简直是笑死人了，显然可以a[tx-1][ty]=1-a[tx-1][ty]或者 a[tx-1][ty]=!a[tx-1][ty]

YTC

优化的循环

1. #include<iostream>
   
2. using namespace std;
   
3. const int dx[]={0,-1,0,1,+0};
   
4. const int dy[]={0,+0,1,0,-1};
   
5. int a[4][4];
   
6. int b[4][4];
   
7. int k[4][4];
   
8. bool judge()
   
9. {
   
10.     for(int i=1;i<=3;i++)
    
11.         for(int j=1;j<=3;j++)
    
12.         if(!b[i][j]) return false;
    
13.     return true;
    
14. }
    
15. int ans,num=0x7fffffff;
    
16. int main()
    
17. {
    
18.     for(int i=1;i<=3;i++)
    
19.         for(int j=1;j<=3;j++)
    
20.         cin>>a[i][j];
    
21.         for(k[1][2]=0;k[1][2]<=1;k[1][2]++)
    
22.         for(k[2][1]=0;k[2][1]<=1;k[2][1]++)
    
23.         for(k[2][3]=0;k[2][3]<=1;k[2][3]++)
    
24.         for(k[3][2]=0;k[3][2]<=1;k[3][2]++)
    
25.     {
    
26.         k[1][1]=a[1][1]^k[1][2]^k[2][1]^1;
    
27.         k[1][3]=a[1][3]^k[1][2]^k[2][3]^1;
    
28.         k[2][2]=a[2][2]^k[1][2]^k[2][1]^k[2][3]^k[3][2]^1;
    
29.         k[3][1]=a[3][1]^k[2][1]^k[3][2]^1;
    
30.         k[3][3]=a[3][3]^k[2][3]^k[3][2]^1;
    
31.         ans=0;
    
32.         for(int i=1;i<=3;i++)
    
33.             for(int j=1;j<=3;j++)
    
34.             b[i][j]=a[i][j];
    
35.         for(int i=1;i<=3;i++)
    
36.             for(int j=1;j<=3;j++)
    
37.                 if(k[i][j])
    
38.         {
    
39.             ans++;
    
40.             for(int ii=0;ii<=4;ii++)
    
41.                 b[i+dx[ii]][j+dy[ii]]=1-b[i+dx[ii]][j+dy[ii]];
    
42.         }
    
43.         if(judge()) num=min(num,ans);
    
44.     }
    
45.     cout<<num;
    
46.     return 0;
    
47. }

复制代码