[codevs1050]棋盘染色 2

试题描述

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

输入

第一行一个整数N(<=100)，接下来N行每行一个长度为5的01串，1表示所在格子已经被染成了黑色，0表示所在格子没有被染色。

输出

输出最少需要对多少个格子进行染色

输入示例

输出示例

数据规模及约定

N(<=100)

题解

状压 dp 一下。设 f(i, S) 表示考虑前 i 行，最后一行情况为集合 S 的最小代价；其中 S 是一个 5 位的 4 进制数，若某一位为 0，则表示第 i 行对应的位置没有染色，若某一位为 x(0 < x < 4)，则表示该位上有染色并且该位置所在的连通分量编号为 x（注意这里的连通分量是指考虑前 i 行时的连通性，因为最终要做到整个图被弄成一个连通分量，所以任意时刻同一连通块必定能够贯穿上下），一行中只有 5 个位置，所以最多产生 3 个连通块，也就是每一位上只可能是 0, 1, 2, 3，所以是 5 位的 4 进制数。

转移时枚举一下下一行在哪些位置染色，然后暴力搞一搞判一判就好了。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

int read() {

    int x = 0, f = 1; char c = getchar();

    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

    return x * f;

}

#define maxn 110

#define maxm 10

char Map[maxn][maxm];

int n, A[maxn][maxm], f[maxn][1030], now[maxm], lst[maxm], fin[maxm], tfin[maxm];

bool iszero(char* S) {

	int l = strlen(S);

	for(int i = 0; i < l; i++) if(S[i] - '0') return 0;

	return 1;

}

int bitcal(int S) {

	int cnt = 0;

	while(S) cnt += (S & 1), S >>= 1;

	return cnt;

}

void Up(int& a, int b) {

	if(a < 0) a = b;

	else a = min(a, b);

	return ;

}

void show(int T[]) {

	for(int i = 0; i < 5; i++) printf("%d%c", T[i], i < 4 ? ' ' : '\n');

	return ;

}

int main() {

	n = read();

	for(int i = 1; i <= n; i++) scanf("%s", Map[i]);

	int up = 1, down = n, cnt = 0;

	while(iszero(Map[up])) up++;

	while(iszero(Map[down])) down--;

	for(int i = up; i <= down; i++) {

		cnt++;

		for(int j = 0; j < 5; j++) A[cnt][j] = Map[i][j] - '0';

	}

	memset(f, -1, sizeof(f));

	f[0][0] = 0;

	int all = (1 << 5) - 1, All = (1 << 10) - 1;

	for(int i = 1; i <= cnt; i++) {

		int reaS = 0;

		for(int j = 4; j >= 0; j--) reaS = reaS << 1 | A[i][j];

		for(int S = 0; S <= all; S++) if((reaS | S) == S) {

			int cnt1 = bitcal(reaS ^ S);

			for(int j = 0; j < 5; j++) now[j] = S >> j & 1;

			for(int tS = 0; tS <= All; tS++) if(f[i-1][tS] >= 0) {

				int tmpS = tS;

				for(int j = 0; j < 5; j++) lst[j] = tmpS % 4, tmpS >>= 2;

				int mx = 0;

				for(int j = 0; j < 5; j++) if(now[j]) {

					if(!j) mx = fin[j] = 1;

					else if(!fin[j-1]) fin[j] = ++mx;

					else fin[j] = fin[j-1];

				}

				else fin[j] = 0;

//				printf("%d _fin: ", cnt1); show(fin);

				mx = 0;

				for(int j = 0; j < 5; j++) mx = max(mx, lst[j]);

				int has[maxm]; memset(has, 0, sizeof(has));

				for(int j = 0; j < 5; j++) if(lst[j]) {

					if(!has[lst[j]] && fin[j]) has[lst[j]] = fin[j];

					else if(fin[j]) {

						fin[j] = has[lst[j]];

						for(int x = j - 1; x >= 0 && fin[x]; x--) fin[x] = has[lst[j]];

						for(int x = j + 1; x < 5 && fin[x]; x++) fin[x] = has[lst[j]];

					}

				}

				bool ok = 1;

				for(int j = 1; j <= mx; j++) if(!has[j]) {

					ok = 0; break;

				}

				if(!ok) continue;

				for(int j = 0; j < 5; j++) tfin[j] = fin[j];

				sort(tfin, tfin + 5);

				int x = unique(tfin, tfin + 5) - tfin;

				if(x > 1) for(int j = 0; j < 5; j++) fin[j] = lower_bound(tfin, tfin + x, fin[j]) - tfin;

//				show(now); show(lst); show(fin);

				tmpS = 0;

				for(int j = 4; j >= 0; j--) tmpS = tmpS << 2 | fin[j];

				Up(f[i][tmpS], f[i-1][tS] + cnt1);

//				printf("%d\n", f[i][tmpS]); putchar('\n');

			}

		}

	}

	int ans = -1;

	for(int S = 0; S <= all; S++) {

		for(int i = 0; i < 5; i++) now[i] = S >> i & 1;

		int reaS = 0;

		for(int i = 4; i >= 0; i--) reaS = reaS << 2 | now[i];

		if(f[cnt][reaS] >= 0) Up(ans, f[cnt][reaS]);

	}

	printf("%d\n", ans);

	return 0;

}

写个状压 dp 真费劲。。。

秒客网

[codevs1050]棋盘染色 2

相关文章