描述

有一個5*N的棋盤，棋盤中的一些格子已經被染成了黑色，你的任務是對最少的格子染色，使得所有的黑色能連成一塊。

http://codevs.cn/problem/1050/

---

分析

CODEVS 題解里有個很良心的人, 我是看了他的才寫的.
http://codevs.cn/wiki/solution/?problem_id=1050
Solution_ID:5329

輪廓線DP.
我開始錯在了把 normalize(b) 放在了if前面, 導致if判斷打了醬油…

采用四進制 (兩個二進制位) 表示輪廓線的狀態, 0為白色格子, 1、2、3為不同的黑格子.

main() :
if (x, y) 是黑點
if 當前狀態 (x, y), 上方的點為黑點:
獲取其強聯通分量的編號, 將當前的格子設為與其相同的強聯通分量編號.
else if 當前狀態 (x, y) 中 y > 0 && 左邊的點為黑點:
獲取其強聯通分量的編號, 將當前的格子設為與其相同的強聯通分量編號.
else: 自己作為一個單獨的強聯通分量(編號為3).

else :
1. 不更改, 直接加入
2. 改成1 =>
if 當前狀態 (x, y), 上方的點為黑點:
獲取其強聯通分量的編號, 將當前的格子設為與其相同的強聯通分量編號.
else if 當前狀態 (x, y), y > 0 && 左邊的點為黑點:
獲取其強聯通分量的編號, 將當前的格子設為與其相同的強聯通分量編號.
else: 自己作為一個單獨的強聯通分量

a 和 b 的 &3 后的結果相差的是什么? => 兩個相鄰的格子吧 => 既然相鄰了又都是黑色的, 那么應屬于一個強聯通分量 => 合并兩個強聯通分量.

這里有點亂 = =
當前格子左上方的格子將要退出輪廓線, 如果它消失, 它所在的強聯通分量可能就會消失, 導致后面出現新的多余的強聯通分量.
=>
if 左上方的格子不是空的, 并且 b 中沒有與它相同強聯通分量編號的格子了. 說明 b 狀態不合法 不能更新答案.

而如果輪廓線上沒有最初編號為1的格子, 后面的格子一定不能與前面的格子相連通了, 也不是合法的狀態.

滿足幾個要求就可以更新答案了.

用到的位運算

<< 2 // 轉移到下個狀態.

>> 8 // 取出當前格子上面格子的強聯通分量編號.

&3 // 取出當前格子左面格子的強聯通分量編號.

x^(a << i)^(b << i) // 把x從第i位開始的兩位由a變為b (a, b都是兩個二進制位).

---

代碼

127ms 492kB
簡化了一下代碼.
看了看代碼高亮發現 state 和 read 好像都是保留字啊, 以后不用了…

#include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 100 + 10; int cur, board[maxn][5], f[2][1<<15]; bool appear;void merge(int& state, int a, int b) {for(int i = 0; i < 12; i+=2)if(((state>>i) & 3) == a) state = state ^ (a<<i) ^ (b<<i); }bool exist(int state, int color) {for(int i = 0; i < 10; i+=2)if(((state>>i) & 3) == color) return 1;return 0; }void normalize(int& state) {if(!exist(state, 2) && exist(state, 3)) {if(appear) merge(state, 3, 2);else { merge(state, 3, 1); appear = 1; }} }void update(int a, int b, int row, int col) {if((a&3) > 0 && (b&3) > 0 && col > 0 && (a&3) != (b&3)) merge(b, max(a&3, b&3), min(a&3, b&3));if(a == 0 || (((b>>10) <= 0 || exist(b, b>>10)) && (((b>>10) == 1) || exist(b, 1)))) {normalize(b);int t = (board[row][col] == 1 || (b&3) == 0) ? 0 : 1;b ^= (b>>10) << 10;f[cur][b] = min(f[cur][b], f[1-cur][a] + t);} }int main() {int n, lasti = 0, lastj = 0;scanf("%d", &n);for(int i = 0; i < n; i++) {char read[5];scanf("%s", read);for(int j = 0; j < 5; j++) {board[i][j] = read[j] - '0';if(board[i][j]) { lasti = i; lastj = j; }}} memset(f, 0x7f, sizeof(f));f[cur][0] = 0;for(int i = 0; i < n; i++) if(i <= lasti)for(int j = 0; j < 5; j++) {if(!board[i][j] && !appear) continue;if(i == lasti && j > lastj) break;cur ^= 1;memset(f[cur], 0x7f, sizeof(f[cur]));for(int k = 0; k < (1<<10); k++) {if((k>>8) > 0) update(k, (k<<2)^(k>>8), i, j);else if((k&3) > 0 && j) update(k, (k<<2)^(k&3), i, j);else update(k, (k<<2)^3, i, j); // new colorif(!board[i][j]) update(k, k<<2, i, j);}}int ans = 0x7fffffff;for(int state = 0; state < (1<<10)-1; state++) if(!exist(state, 2) && !exist(state, 3))ans = min(ans, f[cur][state]);printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的[CODEVS 1050] 棋盘染色 2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。