首页 > 其他 > 详细

Luogu P1764翻转游戏

时间:2019-09-23 00:34:31      阅读:94      评论:0      收藏:0      [点我收藏+]

我代码能力可能有一定的了,要不然不能一遍写出来吧。。

要注意无解的处理!

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 int a[20][20];
 7 int n,ans = -1,k,cnt0;
 8 char ch;
 9 
10 void print(){
11     cout << endl;
12     for(int i = 1;i <= n;i++){
13         for(int j = 1;j <= n;j++)cout << a[i][j];
14         cout << endl;
15     }
16     cout << endl;
17 }
18 
19 void touch(int x,int y){
20     a[x-1][y] ^= 1;
21     a[x][y-1] ^= 1;
22     a[x][y] ^= 1;
23     a[x][y+1] ^= 1;
24     a[x+1][y] ^= 1;
25 }
26 
27 void work0(){
28     for(int i = 1;i <= n;i++)
29         if((k>>(i-1))&1)a[0][i] = 1;
30         else a[0][i] = 0;
31 }
32 
33 void work1(int cur,int cnt){//print();
34     if(cur == n+1){
35         for(int i = 1;i <= n;i++)if(!a[n][i])return;
36         if(ans == -1||ans > cnt)ans = cnt;
37         return;
38     }
39     int v = 0;
40     for(int i = 1;i <= n;i++)if(!a[cur-1][i]){
41         cnt++;
42         touch(cur,i);
43         v |= 1<<(i-1);
44     }
45     work1(cur+1,cnt);
46     for(int i = 1;i <= n;i++)if((v>>(i-1))&1)touch(cur,i);
47 }
48 
49 void work2(int cur,int cnt){//print();
50     if(cur == n+1){
51         for(int i = 1;i <= n;i++)if(a[n][i])return;
52         if(ans == -1||ans > cnt)ans = cnt;
53         return;
54     }
55     int v = 0;
56     for(int i = 1;i <= n;i++)if(a[cur-1][i]){
57         cnt++;
58         touch(cur,i);
59         v |= 1<<(i-1);
60     }
61     work2(cur+1,cnt);
62     for(int i = 1;i <= n;i++)if((v>>(i-1))&1)touch(cur,i);
63 }
64 
65 int main(){
66     cin >> n;
67     for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++){
68         cin >> ch;
69         if(ch == b)a[i][j] = 1;
70         else a[i][j] = 0;
71     }    
72     for(k = 0;k < 1<<n;k++)work0(),work1(1,0),work2(1,0);
73     if(ans != -1)cout << ans;
74     else cout << "Impossible";
75 return 0;
76 }

 

Luogu P1764翻转游戏

原文:https://www.cnblogs.com/Wangsheng5/p/11569869.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!