Submission #69471982

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#define popc __builtin_popcount

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int inf = 1e9;
int T, H, W, bs[10], f[10][129];

int main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> T;
	while(T--) {
		cin >> H >> W;
		vector <string> s(H);
		for(int i = 0; i < H; i++) cin >> s[i];
		memset(bs, 0, sizeof(bs));
		for(int i = 0; i <= H; i++) for(int j = 0; j <= (1 << W); j++) f[i][j] = inf;
		for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) if(s[i][j] == '#') bs[i] |= (1 << j);
		for(int S = 0; S < (1 << W); S++) {
			if((S | bs[0]) != bs[0]) continue;
			f[0][S] = popc(bs[0]) - popc(S);
		}
		for(int i = 1; i < H; i++)
			for(int S = 0; S < (1 << W); S++) {
				if((S | bs[i]) != bs[i]) continue;
				for(int t = 0; t < (1 << W); t++) {
					if(f[i - 1][t] == inf) continue;
					bool fl = 1;
					for(int j = 0; j < W - 1; j++) {
						int p1 = (t >> j) & 1, p2 = (t >> (j + 1)) & 1;
						int c1 = (S >> j) & 1, c2 = (S >> (j + 1)) & 1;
						if(p1 && p2 && c1 && c2) { fl = 0; break; }
					}
					if(!fl) continue;
					f[i][S] = min(f[i][S], f[i - 1][t] + popc(bs[i]) - popc(S));
				}
			} 
		int ans = inf;
		for(int S = 0; S < (1 << W); S++) ans = min(ans, f[H - 1][S]);
		printf("%d\n", ans);
	}
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result