18.05.11 枚举作业

描述

有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时，位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。

输入第一行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。输出一行，如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。样例输入

5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出

来源1681

 1 #include <iostream>
 2 #include <fstream>
 3 #include <stdlib.h>
 4 #include <cstdio>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 20;
 9 int wall[maxn][maxn], use[maxn][maxn];
10 int n, minn = 9999, count0 = 0,flag=0;
11 
12 void init() {
13     scanf("%d", &n);
14     for (int i = 1; i <= n; i++)
15         for (int j = 1; j <= n; j++)
16         {
17             char ch;
18             cin>>ch;
19             if (ch == 'w')wall[i][j] = 0;
20             else wall[i][j] = 1;
21         }
22 }
23 bool guess() {
24     for (int r = 1; r<n; r++)
25         for (int c = 1; c <= n; c++) {
26             use[r + 1][c] = (wall[r][c] + use[r][c] + use[r][c - 1] + use[r][c + 1] + use[r - 1][c]+1) % 2;
27         }
28     for (int c = 1; c <= n; c++)
29         if ((use[n][c - 1] + use[n][c + 1] + use[n-1][c]+use[n][c]) % 2 == wall[n][c])
30             return false;
31     return true;
32 }
33 void solve() {
34     while (1)
35     {
36         if (guess()) {
37             for (int i = 1; i <= n; i++)
38                 for (int j = 1; j <= n; j++)
39                 {
40                     if (use[i][j])count0++;
41                 }
42             minn = min(count0, minn);
43             count0 = 0;
44             flag = 1;
45         }
46         for (int i = 2; i <= n; i++)
47             for (int j = 1; j <= n; j++)
48                 use[i][j] = 0;
49         use[1][1]++;
50         int c = 1;
51         while (use[1][c] > 1) {
52             use[1][c] = 0;
53             use[1][++c]++;
54         }
55         if (c == n + 1)break;
56     }
57 }
58 
59 int main() {
60     init();
61     solve();
62     if (flag)
63         printf("%d
", minn);
64     else
65         printf("inf
");
66     return 0;
67 }

View Code

wa点：1）我居然把n写成了5

2）没有inf输出

3）step是+=，写成=真的是很神了

B:拨钟问题

描述

有9个时钟，排成一个3*3的矩阵。

|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C    

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F    

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I    
(图 1)

现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。

移动    影响的时钟
 
 1         ABDE
 2         ABC
 3         BCEF
 4         ADG
 5         BDEFH
 6         CFI
 7         DEGH
 8         GHI
 9         EFHI

输入9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点、1=3点、2=6点、3=9点。输出输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。样例输入

3 3 0 
2 2 2 
2 1 2

样例输出

4 5 8 9

来源1166

 1 #include <iostream>
 2 #include <fstream>
 3 #include <stdlib.h>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <memory.h>
 7 using namespace std;
 8 
 9 const int maxn = 30;
10 int clock0[10], use[10], res[maxn],state[10];
11 int func[10][10], step = 0,minstep=9999;
12 
13 void funset() {
14     for (int i = 1; i <= 9; i++) {
15         switch (i)
16         {
17         case 1:func[i][1] = 1, func[i][2] = 1, func[i][4] = 1, func[i][5] = 1; break;
18         case 2:func[i][1] = 1, func[i][2] = 1, func[i][3] = 1; break;
19         case 3:func[i][2] = 1, func[i][3] = 1, func[i][5] = 1, func[i][6] = 1; break;
20         case 4:func[i][1] = 1, func[i][4] = 1, func[i][7] = 1; break;
21         case 5:func[i][2] = 1, func[i][4] = 1, func[i][5] = 1, func[i][6] = 1, func[i][8]=1; break;
22         case 6:func[i][3] = 1, func[i][6] = 1, func[i][9] = 1; break;
23         case 7:func[i][4] = 1, func[i][5] = 1, func[i][7] = 1, func[i][8] = 1; break;
24         case 8:func[i][7] = 1, func[i][8] = 1, func[i][9] = 1; break;
25         case 9:func[i][5] = 1, func[i][6] = 1, func[i][8] = 1, func[i][9] = 1; break;
26         }
27     }
28 }
29 void init() {
30     for (int i = 1; i <= 9; i++)
31         {
32             int tmp;
33             scanf("%d", &tmp);
34             clock0[i] = (4 - tmp) % 4;
35         }
36 }
37 bool jud() {
38     for (int i = 4; i <= 9; i++) {
39         if(i<=7&&i>=4)use[i] = (444+clock0[i-3] - state[i-3]) % 4;
40         else if (i == 8)use[i] = (444+clock0[7] - state[7]) % 4;
41         else if (i == 9)use[i] = (444+clock0[5] - state[5]) % 4;
42         for (int j = 1; j <= 9; j++) {
43             state[j] += use[i] * func[i][j];
44         }
45     }
46     for (int i = 1; i <= 9; i++) {
47         if (state[i] % 4 != clock0[i])return false;
48     }
49     step = 0;
50     for (int i = 1; i <= 9; i++)
51         step += use[i];
52     return true;
53 }
54 void solve() {
55     for(int i=0;i<=3;i++)
56         for (int j = 0; j <= 3; j++) 
57             for(int k=0;k<=3;k++)
58         {
59                 use[1] = i, use[2] = j, use[3] = k;
60                 for (int p = 1; p <= 3; p++) {
61                     for (int o = 1; o <= 9; o++) {
62                         state[o] += use[p] * func[p][o];
63                     }
64                 }
65                 if (jud() && step < minstep) {
66                     minstep = step;
67                     int c = 0;
68                     for (int i = 1; i <= 9; i++) {
69                         for (int j = 1; j <= use[i]; j++)
70                             res[++c] = i;
71                     }
72                     break;
73                 }
74                 for (int p = 4; p <= 9; p++)use[p] = 0;
75                 memset(state, 0, sizeof(int) * 10);
76         }
77 }
78 
79 int main() {
80     funset();
81     init();
82     solve();
83     printf("%d", res[1]);
84     for (int i = 2; res[i] != 0; i++)printf(" %d", res[i]);
85     printf("
");
86     return 0;
87 }

View Code

错误点：1）clock在g++编译中可能是某个内置变量，会CE

2）在 jud() 函数中，use的计算如果前面不事先＋444之类的4的倍数，会出现负数，而且这个倍数还要稍微大一点

3）memset要加头文件 <memory.h>

思路：依然是局部枚举，就是前3种方法如果定下来了，后面都能自己得出来

C:特殊密码锁

描述

有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。

然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。

输入两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。输出至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。样例输入

011
000

样例输出

 1 #include <iostream>
 2 #include <fstream>
 3 #include <stdlib.h>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <string>
 7 #include <memory.h>
 8 using namespace std;
 9 
10 const int maxn = 35;
11 int key[maxn], pwd[maxn], press[maxn], aft[maxn], leng, success = 0, step = 0, minstep = 9999;//press-whether to change the status;aft-status after the press
12 
13 void init() {
14     string s1, s2;
15     cin >> s1 >> s2;
16     int l1 = s1.length();
17     for (int i = 0; i < l1; i++) {
18         key[i + 1] = s1[i] - '0';
19         pwd[i + 1] = s2[i] - '0';
20         aft[i + 1] = s1[i] - '0';
21     }
22     leng = l1;
23 }
24 void solve() {
25     for (int op = 0; op <= 1; op++) {
26         memset(press, 0, sizeof(int)*maxn);
27         step = 0;
28         press[1] = op; aft[1] ^= op; aft[2] ^= op;
29         step += op;
30         for (int i = 2; i <= leng; i++) {
31             if (aft[i - 1] != pwd[i - 1]) {
32                 press[i] = 1; step++;
33             }
34             aft[i] ^= press[i];
35             aft[i-1] ^= press[i];
36             aft[i+1] ^= press[i];
37             if (i == leng && aft[i] == pwd[i]) {
38                 success = 1;
39                 minstep = min(step, minstep);
40             }
41         }
42         for (int i = 1; i <= leng; i++)aft[i] = key[i];
43     }
44     if (success)printf("%d
", minstep);
45     else printf("impossible
");
46 }
47 
48 int main() {
49     init();
50     solve();
51     return 0;
52 }

View Code

错误点：在 solve() 函数的循环中一定要把之前被改变的变量清零

思路：局部枚举枚举第一个

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。