HDU 1882--Strange Billboard(位運算+枚舉)，hdu1882--strange
位運算http://c.biancheng.net/cpp/html/101.html
在很多情況下（比如翻棋子）在搜索時涉及大量枚舉往往導致超時，位運算則很好地解決了這個問題，方便又快捷
HDU 1882 Strange Billboard
http://acm.hdu.edu.cn/showproblem.php?pid=1882
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 813 Accepted Submission(s): 348
Problem Description
The marketing and public-relations department of the Czech Technical University has designed a new reconfigurable mechanical Flip-Flop Bill-Board (FFBB). The billboard is a regular two-dimensional grid of R ×C square tiles made of plastic. Each plastic tile is white on one side and black on the other. The idea of the billboard is that you can create various pictures by flipping individual tiles over. Such billboards will hang above all entrances to the university and will be used to display simple pictures and advertise upcoming academic events.
To change pictures, each billboard is equipped with a ”reconfiguration device”. The device is just an ordinary long wooden stick that is used to tap the tiles. if you tap a tile, it flips over to the other side, i.e., it changes from white to black or vice versa. Do you agree this idea is very clever?
Unfortunately, the billboard makers did not realize one thing. The tiles are very close to each other and their sides touch. Whenever a tile is tapped, it takes all neighboring tiles with it and all of them flip over together. Therefore, if you want to change the color of a tile, all neighboring tiles change their color too. Neighboring tiles are those that touch each other with the whole side. All inner tiles have 4 neighbors, which means 5 tiles are flipped over when tapped. Border tiles have less neighbors, of course.
For example, if you have the billboard configuration shown in the left picture above and tap the tile marked with the cross, you will get the picture on the right. As you can see, the billboard reconfiguration is not so easy under these conditions. Your task is to find the fastest way to ”clear” the billboard, i.e., to flip all tiles to their white side.
Input
The input consists of several billboard descriptions. Each description begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 16) specifying the billboard size. Then there are R lines, each containing C characters. The characters can be either an uppercase letter “X” (black) or a dot “.” (white). There is one empty line after each map.
The input is terminated by two zeros in place of the board size.
Output
For each billboard, print one line containing the sentence “You have to tap T tiles.”, where T is the minimal possible number of taps needed to make all squares white. if the situation cannot be solved, output the string “Damaged billboard.” instead.
Sample Input
5 5
XX.XX
X.X.X
.XXX.
X.X.X
XX.XX
5 5
.XX.X
.....
..XXX
..X.X
..X..
1 5
...XX
5 5
...X.
...XX
.XX..
..X..
.....
8 9
..XXXXX..
.X.....X.
X..X.X..X
X.......X
X.X...X.X
X..XXX..X
.X.....X.
..XXXXX..
0 0
Sample Output
You have to tap 5 tiles.
Damaged billboard.
You have to tap 1 tiles.
You have to tap 2 tiles.
You have to tap 25 tiles.
這題剛開始按照一般枚舉寫 很高興的 TML了 (ノへ￣、) 代碼如下
![]()
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int dir[][2] = { -1, 0, 0, -1, 0, 0, 0, 1, 1, 0 };
5 int n, m, map[16][16], flip[16][16];//flip最終翻轉情況的數組
6 //int opt[16][16];
7 void init(){
8 char x;
9 memset(map, 0, sizeof(map));
10 for (int i = 0; i < n; i++){
11 for (int j = 0; j < m; j++){
12 cin >> x;
13 if (x == 'X')
14 map[i][j] = 1;
15 }
16 }
17 }
18 //用來查看當前棋子的顏色
19 int get_colour(int x, int y){
20 int a = map[x][y], i;
21 for (i = 0; i < 5; i++){
22 int x2 = x + dir[i][0], y2 = y + dir[i][1];
23 if (x2 >= 0 && x2 < n&&y2 >= 0 && y2 < m){
24 a += flip[x2][y2];
25 }
26 }
27 return a % 2;
28 }
29 int calc(){
30 int i, j, cnt = 0;
31 for (i = 1; i < n; i++){
32 for (j = 0; j < m; j++){
33 if (get_colour(i - 1, j))
34 flip[i][j] = 1;
35 }
36 }
37 for (i = 0; i < m; i++){
38 if (get_colour(n - 1, i))
39 return -1;
40 }
41 for (i = 0; i < n; i++){
42 for (j = 0; j < m; j++){
43 cnt += flip[i][j];
44 }
45 }
46 return cnt;
47 }
48 int main(){
49 while (cin >> n >> m, n || m){
50 int cnt = -1, i, j, num;
51 init();
52 for (i = 0; i < 1 << m; i++){
53 memset(flip, 0, sizeof(flip));
54 for (j = 0; j < m; j++){
55 flip[0][m - j - 1] = i >> j & 1;
56 }
57 num = calc();
58 if (num >= 0 && (cnt<0 || cnt>num)){
59 cnt = num;
60 //memcpy(opt, flip, sizeof(flip));
61 }
62 }
63 if (cnt < 0)
64 cout << "Damaged billboard.\n";
65 else{
66 cout << "You have to tap " << cnt << " tiles.\n";
67 //for (i = 0; i < n; i++){
68 //for (j = 0; j < m; j++){
69 //cout << opt[i][j] << ' ';
70 //}
71 //cout << "\r\n";
72 //}
73 }
74 }
75 return 0;
76 }
View Code
後來才發現這樣寫時間復雜度是 nm2^n雖然最大測試數據為15 但超時還是難免的
最終糾結了好久的位運算，加上代碼優化終於過了
ac 代碼如下
![]()
1 /******************************************************
2 & 按位與(交集)
3 | 按位或(並集)
4 ^ 按位異或(翻轉棋子)
5 ~ 取反
6 << 左移
7 >> 右移
8 S|1<<i 向集合中加入第i個元素
9
10 for(int i=0;i<1<<n;s++) (枚舉集合)
11 *******************************************************/
12 #include<iostream>
13 #include<cstring>
14 using namespace std;
15 #define inf 0x7fffffff
16 #define min(a,b) a<b?a:b
17 int n, m, mpt[17];
18 char map[17][17];
19 void init(){
20 int i, j;
21 memset(map, 0, sizeof(map));
22 memset(mpt, 0, sizeof(mpt));
23 if (n >= m){
24 for (i = 0; i < n; i++){
25 cin >> map[i];
26 for (j = 0; j < m; j++){
27 if (map[i][j] == 'X')
28 mpt[i] |= 1 << j;
29 //cout << mpt[i] << endl;
30 //如果輸入字符為X,加入對應元素到集合
31 }
32 }
33 }
34 else{ //當列大於行,轉置矩陣存儲
35 for (i = 0; i < n; i++){
36 cin >> map[i];
37 for (j = 0; j < m; j++){
38 if (map[i][j] == 'X')
39 mpt[j] |= 1 << i;
40 }
41 }
42 n ^= m ^= n ^= m;
43 }
44 }
45 int find_set(){
46 int minn = inf, tmp[17], sign[17], i, j, k, cnt;
47 for (i = 0; i < 1 << m; i++){
48 for (j = 0; j < n; j++)
49 tmp[j] = mpt[j];
50 for (j = 0; j < n; j++){
51 //以每一行的上一行為參照翻轉,判斷最後一行狀態即可
52 sign[j] = j == 0 ? i : tmp[j - 1];
53 tmp[j] ^= sign[j];
54 tmp[j] ^= sign[j] << 1 & ((1 << m) - 1);
55 tmp[j] ^= sign[j] >> 1;
56 tmp[j + 1] ^= sign[j];
57 //一次翻轉當前行,左右下(左端邊界判斷!!!!!)
58 }
59 if (!tmp[n - 1]){
60 cnt = 0;
61 for (j = 0; j < n; j++){
62 for (k = sign[j]; k>0; k >>= 1){
63 if (k & 1)
64 cnt++;
65 }
66 }
67 minn = min(minn, cnt);
68 }
69 }
70 return minn;
71 }
72
73 int main(){
74 while (cin >> n >> m, m || n){
75 init();
76 int minn = find_set();
77 if (minn == inf)
78 cout << "Damaged billboard.\n";
79 else
80 cout << "You have to tap " << minn << " tiles.\n";
81 }
82 return 0;
83 }
View Code
同樣的位運算在很多地方都可以應用進來，能起到出其不意的效果
swust oj 781 牛喝水
牛喝水
Time limit(ms): 1000
Memory limit(kb): 65535
Submission: 4
Accepted: 4
Accepted
The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing cool water) or upside-down (a position which holds no water). They want all 20 water bowls to be right-side-up and thus use their wide snouts to flip bowls.
Their snouts, though, are so wide that they flip not only one bowl but also the bowls on either side of that bowl (a total of three or -- in the case of either end bowl -- two bowls).
Given the initial state of the bowls (1=undrinkable, 0=drinkable -- it even looks like a bowl), what is the minimum number of bowl flips necessary to turn all the bowls right-side-up?
Description
Line 1: A single line with 20 space-separated integers
Input
Line 1: The minimum number of bowl flips necessary to flip all the bowls right-side-up (i.e., to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the bowls to 20 0's.
Output
1
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
Sample Input
1
3
Sample Output
Explanation of the sample:
Flip bowls 4, 9, and 11 to make them all drinkable:
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state]
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4]
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]
題目大意：一只牛能把碗翻轉過來，(由於嘴太大 ^_^ )同時會把他左右的碗全部翻轉,1代表需要翻轉的碗，問最少可以幾次把碗全部翻轉（0表示）
這道題吶，用dfs 也能做 ，以前就是dfs a掉的，今天做了位運算後想了想這不就是一個行為1，列為20的位位運算嗎，（上面的說過行大於列就轉置，不然第一行枚舉２^２０，，轉置了就只有兩種可能了）～～
先上dfs的代碼 100ms（反正不低於100）
![]()
1 #include<iostream>
2 using namespace std;
3 int bowl[21], step, flag;
4 int range()
5 {
6 int i;
7 for (i = 0; i<20; i++)
8 if (bowl[i] == 1)
9 return 0;
10 return 1;
11 }
12 void turn(int i)
13 {
14 bowl[i] = !bowl[i];
15 if (i>0)
16 bowl[i - 1] = !bowl[i - 1];
17 if (i<19)bowl[i + 1] = !bowl[i + 1];
18 }
19 void DFS(int i, int dp)
20 {
21 if (step == dp)
22 {
23 flag = range();
24 return;
25 }
26 if (i >= 20 || flag) return;
27 turn(i);
28 DFS(i + 1, dp + 1);
29 turn(i);
30 DFS(i + 1, dp);
31 }
32 int main()
33 {
34 int i;
35 for (i = 0; i < 20; i++)
36 cin >> bowl[i];
37 for (step = 0; step<20; step++)
38 {
39 flag = 0;
40 DFS(0, 0);
41 if (flag) break;
42 }
43 cout << step << endl;
44 return 0;
45 }
View Code
用位運算枚舉0ms秒過啊~~~
![]()
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 #define inf 0x7fffffff
5 #define min(a,b) a<b?a:b
6 int mpt[20], tmp[20], sign[20];
7 int main(){
8 int i, j, cnt, minn = inf, x;
9 for (j = 0; j < 20; j++){
10 cin >> x;
11 if (x)
12 mpt[j] |= 1 << 0;
13 }
14 //行為1，列為20直接轉置
15 for (i = 0; i < 1 << 1; i++){
16 for (j = 0; j < 20; j++)
17 tmp[j] = mpt[j];
18 for (j = 0; j < 20; j++){
19 sign[j] = j == 0 ? i : tmp[j - 1];
20 tmp[j] ^= sign[j];
21 tmp[j + 1] ^= sign[j];
22 }
23 if (!tmp[19]){
24 cnt = 0;
25 for (j = 0; j < 20; j++)
26 if (sign[j] & 1)
27 cnt++;
28 }
29 minn = min(minn, cnt);
30 }
31 cout << minn << endl;
32 return 0;
33 }
View Code
