[CODEVS 1050] 棋盘染色 2

描述

有一个5*N的棋盘，棋盘中的一些格子已经被染成了黑色，你的任务是对最少的格子染色，使得所有的黑色能连成一块。

分析

CODEVS 题解里有个很良心的人, 我是看了他的才写的. ?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的格子, 后面的格子一定不能与前面的格子相连通了, 也不是合法的状态.

满足几个要求就可以更新答案了.

用到的位运算

代码

127ms 492kB 简化了一下代码. 看了看代码高亮发现 state 和 read 好像都是保留字啊, 以后不用了…

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;}

，人生重要的不是所站的位置，而是所朝的方向