华师一附中OI组

标题: P2040 打开所有的灯 [打印本页]

---

作者: admin    时间: 2018-5-17 13:27
标题: P2040 打开所有的灯
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
说明
这个题水不水，就看你怎么考虑了。。。。

---

作者: admin    时间: 2018-6-9 16:41
这个题很值得一做，大家都认真做做！我的程序一向是值得学习的，请看我的

---

作者: 黄煦喆    时间: 2018-6-9 19:16

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    时间: 2018-6-9 19:18
第一种做法，每个开关都可以按1下，按2下及以上是没有意义的，所以枚举每个开关按与不按，穷举9个开关的状态。

---

作者: admin    时间: 2018-6-9 19:19
第二种做法，dfs，枚举000000000-111111111之间的所有数字，判断

---

作者: admin    时间: 2018-6-9 19:19
第三种，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. }
    

复制代码

---

作者: 张笑宇    时间: 2018-6-9 19:34
来一发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. }
    

复制代码

---

作者: 张笑宇    时间: 2018-6-9 19:35
请教孙老师：为什么不对？？？

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    时间: 2018-6-9 21:07
评点下上面两个同学的程序
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    时间: 2018-6-10 16:10


优化的循环

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. }

复制代码

---

作者: YTC    时间: 2018-6-10 16:32

YTC 发表于 2018-6-10 16:10
9重循环

广搜

1. <div class="blockcode"><blockquote>#include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. const int dx[]={0,-1,0,1,+0};
   
5. const int dy[]={0,+0,1,0,-1};
   
6. queue<int> q;
   
7. int step[512];
   
8. int a[5][5];
   
9. int st;
   
10. int hsh()
    
11. {
    
12.     int ret=0;
    
13.     for(int i=1;i<=3;i++)
    
14.         for(int j=1;j<=3;j++)
    
15.         ret=ret*2+a[i][j];
    
16.     return ret;
    
17. }
    
18. void unzip(int ret)
    
19. {
    
20.     for(int i=3;i>=1;i--)
    
21.         for(int j=3;j>=1;j--)
    
22.     {
    
23.         a[i][j]=ret&1;
    
24.         ret/=2;
    
25.     }
    
26. }
    
27. int main()
    
28. {
    
29.     for(int i=1;i<=9;i++)
    
30.     {
    
31.         int t;
    
32.         cin>>t;
    
33.         st=st*2+t;
    
34.     }
    
35.     q.push(st);
    
36.     step[st]=0;
    
37.     while(!q.empty())
    
38.     {
    
39.         int x=q.front();
    
40.         q.pop();
    
41.         if(x==511) {cout<<step[x];return 0;}
    
42.         unzip(x);
    
43.         for(int i=1;i<=3;i++)
    
44.             for(int j=1;j<=3;j++)
    
45.         {
    
46.             for(int t=0;t<=4;t++)
    
47.             a[i+dx[t]][j+dy[t]]=1-a[i+dx[t]][j+dy[t]];
    
48.             int ret=hsh();
    
49.             step[ret]=step[x]+1;
    
50.             q.push(ret);
    
51.             for(int t=0;t<=4;t++)
    
52.             a[i+dx[t]][j+dy[t]]=1-a[i+dx[t]][j+dy[t]];
    
53.         }
    
54.     }
    
55.     return 0;
    
56. }

复制代码

---

作者: YTC    时间: 2018-6-10 16:53
深搜

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. }

复制代码

---

作者: 李思矿    时间: 2018-6-10 17:16
孙老师，【题目总结】P2040打开所有的灯

---

作者: admin    时间: 2018-6-10 17:30
为什么要你们把程序贴上来呢？请看我手动摘取的李思旷的程序片段

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';

---

作者: YTC    时间: 2018-6-13 13:23

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

数组应该开5乘5的

---

作者: admin    时间: 2018-6-13 20:46
楼上的各位都做得很好！ 这个题目里面可以学到很多的东西！

---

作者: 张笑宇    时间: 2018-6-16 20:26
终于用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. }
    

复制代码

---

作者: 张笑宇    时间: 2018-6-16 21:04
新颖！！！
枚举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. }
    

复制代码

---

作者: 吴语林    时间: 2018-6-25 06:25

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. }
    

复制代码

---

作者: lyc    时间: 2018-7-2 19:34
应该用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. }

复制代码

---

作者: admin    时间: 2019-10-27 19:14
楼上Y同学，把我的跳转表技术用得很好，要是能把7-11行的那个也用达标写出来就更好了。你想想看。

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2