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

楼上Y同学，把我的跳转表技术用得很好，要是能把7-11行的那个也用达标写出来就更好了。你想想看。

lyc

应该用bfs快些,不过数据水……dfs加个最优性剪纸就过了……数据大应该T到飞起

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstdio>
   
4. #include<cstring>
   
5. const int oo = 0x3f3f3f3f;
   
6. const int N = 5;
   
7. using namespace std;
   
8. int a[5][5];
   
9. int vis[5][5];
   
10. int fx[5] = {+0, +1, -1, +0, +0};
    
11. int fy[5] = {+0, +0, +0, -1, +1};
    
12. int ans = oo;
    
13. void change(int x, int y)
    
14. {
    
15.     for(int i=0; i<=4; i++)
    
16.     {
    
17.         a[x+fx[i]][y+fy[i]] = 1 - a[x+fx[i]][y+fy[i]];
    
18.     }
    
19. }
    
20. bool check()
    
21. {
    
22.     for(int i=1; i<=3; i++)
    
23.         for(int j=1; j<=3; j++)
    
24.             if(a[i][j] == 0)
    
25.                 return 0;
    
26.     return 1;
    
27. }
    
28. void dfs(int now)
    
29. {
    
30.     if(now > ans) return;
    
31.     if(now > 9)
    
32.         return ;
    
33.     for(int i=1; i<=3; i++)
    
34.         for(int j=1; j<=3; j++)
    
35.         {
    
36.             if(!vis[i][j]){
    
37.                 change(i, j);
    
38.                 vis[i][j] = 1;
    
39.                 if(check()){
    
40.                     ans = min(ans, now);
    
41.                     change(i, j);
    
42.                     vis[i][j] = 0;
    
43.                     return;
    
44.                 }
    
45.                 dfs(now+1);
    
46.                 change(i, j);
    
47.                 vis[i][j] = 0;
    
48.             }
    
49.         }
    
50.         dfs(now+1);
    
51. }
    
52. int main()
    
53. {
    
54.     for(int i=1; i<=3; i++)
    
55.         for(int j=1; j<=3; j++)
    
56.             cin>>a[i][j];
    
57.     dfs(1);
    
58.     cout<<ans;
    
59.     return 0;
    
60. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int a[40];
    
14. struct node
    
15. {
    
16.         int er,step,last;
    
17. };
    
18. int main()
    
19. {
    
20.         queue<node> q;
    
21.         for(int i=1;i<=9;i++)
    
22.                 scanf("%d",&a[i]);
    
23.         int z=0;
    
24.         for(int i=9,j=1;i>=1;i--,j*=2)
    
25.                 z+=(a[i]*j);
    
26.         node l={z,0,-1};
    
27.         q.push(l);
    
28.         node u;
    
29.         int t[40];
    
30.         while(!q.empty())
    
31.         {
    
32.                 u=q.front();q.pop();
    
33.                 if(u.er==511)
    
34.                 {
    
35.                         printf("%d",u.step);
    
36.                         return 0;
    
37.                 }
    
38.                 z=u.er;
    
39.                 for(int i=1,j=256;i<=9;i++,j/=2)
    
40.                 {
    
41.                         t[i]=z/j;
    
42.                         z%=j;
    
43.                 }
    
44.                 for(int i=1;i<=9;i++)
    
45.                 {
    
46.                         if(i==u.last) continue;
    
47.                         t[i]^=1;
    
48.                         if(i-3>=1)
    
49.                                 t[i-3]^=1;
    
50.                         if(i+3<=9)
    
51.                                 t[i+3]^=1;
    
52.                         if((i-1)%3!=0)
    
53.                                 t[i-1]^=1;
    
54.                         if((i+1)%3!=1)
    
55.                                 t[i+1]^=1;
    
56.                         z=0;
    
57.                         for(int k=9,j=1;k>=1;k--,j*=2)
    
58.                                 z+=(t[k]*j);
    
59.                         node t2={z,u.step+1,i};
    
60.                         q.push(t2);
    
61.                         t[i]^=1;
    
62.                         if(i-3>=1)
    
63.                                 t[i-3]^=1;
    
64.                         if(i+3<=9)
    
65.                                 t[i+3]^=1;
    
66.                         if((i-1)%3!=0)
    
67.                                 t[i-1]^=1;
    
68.                         if((i+1)%3!=1)
    
69.                                 t[i+1]^=1;
    
70.                 }       
    
71.         }
    
72.         return 0;
    
73. }
    

复制代码

张笑宇

新颖！！！
枚举2，4，6，8位的状态！！！

1. #include<iostream>
   
2. using namespace std;
   
3. const int mx=4;
   
4. const int mm=10;
   
5. int a[mx][mx],i,j,k,v;///a地图
   
6. int ans=999;
   
7. int main()
   
8. {
   
9.     for (i=1; i<=mx-1; i++)
   
10.         for (j=1; j<=mx-1; j++) cin>>a[i][j];
    
11. 
    
12.     for (i=0; i<=1; i++)///2是否按
    
13.         for (j=0; j<=1; j++)///4是否按
    
14.             for (k=0; k<=1; k++)///6是否按
    
15.                 for (v=0; v<=1; v++)///8是否按
    
16.                 {
    
17.                     int now[mx][mx];
    
18.                     now[1][1]=(i+j+a[1][1])%2;
    
19.                     now[1][3]=(i+k+a[1][3])%2;
    
20.                     now[3][1]=(j+v+a[3][1])%2;
    
21.                     now[3][3]=(k+v+a[3][3])%2;///算出四个角上的
    
22.                     now[2][2]=(i+j+k+v+a[2][2])%2;///中间的
    
23.                     int s1=0,s2=0,s3=0,s4=0,s5=0;
    
24.                     if (now[1][1]!=1) s1=1,now[1][1]=1;///(1,1)按了
    
25.                     if (now[1][3]!=1) s2=1,now[1][3]=1;///(1,3)按了
    
26.                     if (now[3][1]!=1) s3=1,now[3][1]=1;///(3,1)按了
    
27.                     if (now[3][3]!=1) s4=1,now[3][3]=1;///(3,3)按了
    
28.                     if (now[2][2]!=1) s5=1,now[2][2]=1;///(2,2)按了
    
29.                     now[1][2]=(s1+s2+s5+i+a[1][2])%2;
    
30.                     now[2][1]=(s1+s3+s5+j+a[2][1])%2;
    
31.                     now[2][3]=(s2+s4+s5+k+a[2][3])%2;
    
32.                     now[3][2]=(s3+s4+s5+v+a[3][2])%2;///再算十字架上的
    
33.                     bool b=true;
    
34.                     for (int aa=1;aa<=3;aa++)
    
35.                         for (int bb=1;bb<=3;bb++)
    
36.                             if (now[aa][bb]==0) b=false;
    
37.                     if (b)
    
38.                     {
    
39.                         int sum=s1+s2+s3+s4+s5+i+j+k+v;
    
40.                         ans=min(ans,sum);
    
41.                     }
    
42.                 }
    
43.     cout<<ans;
    
44.     return 0;
    
45. }
    

复制代码

张笑宇

终于用bfs过了！！！

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][mm],n[mm],x[mm],y[mm];///n步数
   
7. int i,j,k,head,tail;
   
8. bool cmp(int t)
   
9. {
   
10.     for (int ii=1; ii<=3; ii++)
    
11.         for (int jj=1; jj<=3; jj++)
    
12.             if (a[ii][jj][t]==0) return false;
    
13.     return true;
    
14. }
    
15. void change(int tx,int ty,int t)
    
16. {
    
17.     a[tx-1][ty][t]=1-a[tx-1][ty][t];
    
18.     a[tx+1][ty][t]=1-a[tx+1][ty][t];
    
19.     a[tx][ty-1][t]=1-a[tx][ty-1][t];
    
20.     a[tx][ty+1][t]=1-a[tx][ty+1][t];
    
21.     a[tx][ty][t]=1-a[tx][ty][t];
    
22. }
    
23. int main()
    
24. {
    
25.     for (i=1; i<=3; i++)
    
26.         for (j=1; j<=3; j++) cin>>a[i][j][1];
    
27.     head=1,tail=2,x[1]=1,y[1]=1;
    
28.     while (head<=tail)
    
29.     {
    
30.         if (cmp(head))
    
31.         {
    
32.             cout<<n[head];
    
33.             return 0;
    
34.         }
    
35.         int nx=x[head];
    
36.         int ny=y[head];
    
37.         change(nx,ny,head);
    
38. 
    
39.         for (i=1; i<=3; i++)
    
40.             for (j=1; j<=3; j++)
    
41.                 a[i][j][tail]=a[i][j][head];
    
42.         n[tail]=n[head]+1;
    
43.         if (x[head]==3)
    
44.             x[tail]=1,y[tail]=y[head]+1;
    
45.         else x[tail]=x[head]+1,y[tail]=y[head];
    
46.         tail++;
    
47. 
    
48.         change(nx,ny,head);
    
49. 
    
50.         for (i=1; i<=3; i++)
    
51.             for (j=1; j<=3; j++)
    
52.                 a[i][j][tail]=a[i][j][head];
    
53.         n[tail]=n[head];
    
54.         if (x[head]==3)
    
55.             x[tail]=1,y[tail]=y[head]+1;
    
56.         else x[tail]=x[head]+1,y[tail]=y[head];
    
57.         tail++;
    
58. 
    
59.         head++;
    
60.     }
    
61.     return 0;
    
62. }
    

复制代码

admin

楼上的各位都做得很好！ 这个题目里面可以学到很多的东西！

YTC

YTC 发表于 2018-6-10 16:10
优化的循环

数组应该开5乘5的

admin

为什么要你们把程序贴上来呢？请看我手动摘取的李思旷的程序片段

1. string act(string a,int pos)
   
2. {
   
3.     string re=a;
   
4.     re[pos]=(a[pos]='0'?'1':'0');
   
5.     if(pos%3!=0) re[pos-1]=(a[pos-1]='0')?'1':'0';
   
6.     if(pos%3!=2) re[pos+1]=(a[pos+1]='0')?'1':'0';
   
7.     if(pos/3!=0) re[pos-3]=(a[pos-3]='0')?'1':'0';
   
8.     if(pos/3!=2) re[pos+3]=(a[pos+3]='0')?'1':'0';
   
9.     return re;
   
10. }

复制代码

大家注意到没有 re[pos-1]=(a[pos-1]='0')?'1':'0'; 要改成 re[pos-1]=(a[pos-1]=='0')?'1':'0';  两个等于号！！！！  而且也没有必要 最好写成 re[pos-1]=(a[pos-1]=='0')+'0';

李思矿

孙老师，【题目总结】P2040打开所有的灯

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[5][5];
   
6. bool v[3][3];
   
7. bool judge()
   
8. {
   
9.     for(int i=1;i<=3;i++)
   
10.         for(int j=1;j<=3;j++)
    
11.         if(!a[i][j]) return false;
    
12.     return true;
    
13. }
    
14. int num=0x7fffffff;
    
15. int ans;
    
16. /*void dfs(int k)
    
17. {
    
18.     cout<<k;
    
19.     if(k>=9) return ;
    
20.     if(judge()) {ans=min(ans,k);return;}
    
21.     if(!judge())
    
22.     {
    
23.     for(int i=1;i<=3;i++)
    
24.         for(int j=1;j<=3;j++)
    
25.             if(!v[i][j])
    
26.     {
    
27.         v[i][j]=1;
    
28.         a[i][j]=1-a[i][j];
    
29.         for(int t=0;t<=3;t++)
    
30.             a[i+dx[t]][j+dy[t]]=1-a[i+dx[t]][j+dy[t]];
    
31.         dfs(k+1);
    
32.         a[i][j]=1-a[i][j];
    
33.         for(int t=0;t<=3;t++)
    
34.             a[i+dx[t]][j+dy[t]]=1-a[i+dx[t]][j+dy[t]];
    
35.         v[i][j]=0;
    
36.     }
    
37.     }
    
38. }*/
    
39. void dfs(int i,int j)
    
40. {
    
41.     if(j>3)
    
42.     {
    
43.         i++;
    
44.         j=1;
    
45.     }
    
46.     if(i>3)
    
47.     {
    
48.         if(judge())num=min(num,ans);
    
49.         return;
    
50.     }
    
51.     else{
    
52.         ans++;
    
53.         for(int t=0;t<=4;t++)
    
54.             a[i+dx[t]][j+dy[t]]=1-a[i+dx[t]][j+dy[t]];
    
55.         dfs(i,j+1);
    
56.         for(int t=0;t<=4;t++)
    
57.             a[i+dx[t]][j+dy[t]]=1-a[i+dx[t]][j+dy[t]];
    
58.         ans--;
    
59.         dfs(i,j+1);
    
60.     }
    
61. }
    
62. int main()
    
63. {
    
64.     for(int i=1;i<=3;i++)
    
65.         for(int j=1;j<=3;j++)
    
66.          cin>>a[i][j];
    
67.     dfs(1,1);
    
68.     cout<<num;
    
69.     return 0;
    
70. }

复制代码