P2040 打开所有的灯

吴语林

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

应该用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

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