uva10318(dfs+剪枝)

uva10318(dfs+剪枝)

題意:

給出一個最多面板,上面有很多按鈕,亮著或沒亮,初始是全部沒亮;從左上到右下,編號從1開始;,

現在我們給出一個3*3的矩陣,作為按鈕規則;

例如

.*.

***

.*.

也就是你按任意建,都把這個建單做是這個3*3矩陣的中間,按照這個圖,也就是按一個鍵,則這個建還有它的上下左右,狀態全都轉變(如果它已經沒有上一行了,則忽略);

給出r,c代表幾行幾列

然後給出一個固定的3*3的矩陣;表示按鈕的規則

問最少按幾個全部按鈕都亮;

思路:

首先算出每一個按鈕的影響有哪幾個,用二進制壓縮;

影響編號1的,則第一位是1,不影響的按鈕位置用0;

然後dfs直接暴力;

注意有一個剪枝可以減少很多時間,就是你已經遍歷到第n行,如果第n-2行還有沒亮的按鈕,則就直接退出,因為一個按鈕最多影響到它上一行,上兩行沒亮的就永遠不會亮了;

#include
#include
#include
#define ll long long
using namespace std;

const int N = 30;
struct pos {
	int x,y;
}p[N];
char g[3][3];
int res[N];
int temp[N];
ll s[N];
bool ok;
int num,r,c,ans;

void init() {
	for(int i = 0; i < (r * c); i++) {
		int rr = i / c;
		int cc = i % c;
		for(int j = 0; j < num;j++) {
			int x = rr + p[j].x;
			int y = cc + p[j].y;
			if(x < 0 || y < 0 || x >= r || y >= c)
				continue;
			ll num = (x * c + y);
			s[i] |= (1 << num);
		}
	}
}

void dfs(int cur,int S,int len) {
	if(S == ((1 << (r * c)) - 1) && len < ans) {
		ok = 1;
		for(int i = 0; i < r * c; i++) {
			res[i] = temp[i];
		}
		return;
	}
	if((cur / c) >= 2) {
		int k = (cur/c) - 2;
		for(int i = k * c; i < k * c + c; i++) {
			if(!(S & (1 << i)))
				return ;
		}
	}
	if(cur == (r * c))
		return;
	temp[cur] = 1;
	dfs(cur + 1, S ^ s[cur],len + 1);
	temp[cur] = 0;
	dfs(cur + 1, S, len);
}
int main() {
	int cas = 1;
	while(scanf("%d%d",&r, &c) == 2) {
		for(int i = 0 ; i < 3; i++) {
			scanf("%s",g[i]);
		}
		ok = 0;
		memset(s, 0, sizeof(s));
		memset(temp, 0, sizeof(temp));
		num = 0;
		ans = 0x3f3f3f3f;
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(g[i][j] == '*') {
					p[num].x = i - 1;
					p[num++].y = j - 1;
				}
			}
		}
		init();
		printf("Case #%d\n",cas++);
		dfs(0,0,0);
		bool f = 0;
		if(ok) {
			for(int i = 0 ; i < r * c; i++) {
				if(res[i] == 1) {
					if(f)
						printf(" ");
					if(!f)
						f = 1;
					printf("%d",i + 1);
				}
			}
		}
		if(!ok)
			printf("Impossible.");
		printf("\n");
	}
}