uva 1548 - The Game of Master-Mind(dfs+剪枝)

題目鏈接：uva 1548 - The Game of Master-Mind

題目大意：現在ACM公司要開發一個手游，游戲大致為猜數字，一開始給出p，c和m，p為要猜數字的個數，c為每個數字的最大上限，m為已經猜過的次數，每次猜完系統會給出相應的回復提示，所以接下來有2*m行為前m次的提示。每組提示分兩行，一行是當前猜的數字分別有哪些，一行是代表說黑點個數和白點個數，所謂黑點個數即當前猜的數字有多少個與答案的位置且顏色均相同（題目中用數字代表顏色），白點則是顏色相同，位置不同的點。要注意的是黑點和白點是一一對應的，例：ans：1 1 2 guess：2 2 1，這種情況下白點個數為2，不是3，就是ans中的2只能對應guess中的一個2，而且如果是黑點的話，就不能算成是白點。現在要求說找出與答案最相近的序列，即滿足先前所猜的m次的序列，並且要求字典序最小。

解題思路：dfs，不過光dfs的話，復雜度為100^10。當時因為題目中給的限定條件特別多，所以如果在過程中對黑點白點的情況進行判斷，時間上是沒有問題的。

但是在判斷黑點和白點的時候要注意，統計時要統計黑點個數和點數總和，因為如果將黑點和白點分開計算的話會比較麻煩，因為會有說guess1：2 1，黑1，白0，這樣的話ans為1 1是滿足的，但是在dfs0層是，ans中的第一個1就變成了白點，如果剪枝為白點個數為0返回就錯了。我的處理方法就感覺像是可以先向黑點預支一樣，但是預支也有額度，如果超過現存黑點的個數也是不行的。

#include 
#include 

const int N = 105;
const int M = 15;

int p, c, m, b[N], w[N], ans[M];
int g[N][M], l[N][N], r[N][N];
int cnt[N], sum[N];

void init () {
	memset(l, 0, sizeof(l));
	memset(r, 0, sizeof(r));
	memset(cnt, 0, sizeof(cnt));
	memset(sum, 0, sizeof(sum));

	scanf("%d%d%d", &p, &c, &m);

	for (int i = 0; i < m; i++) {

		for (int j = 0; j < p; j++) {
			scanf("%d", &g[i][j]);
			r[i][g[i][j]]++;
		}
		scanf("%d%d", &b[i], &w[i]);
	}
}

inline bool judge (int x, int d) {
	
	for (int i = 0; i < m; i++) {
		if (x == g[i][d]) {
			if (b[i] == cnt[i]) return false;
		} else if (l[i][x] < r[i][x]) {
			if (sum[i] >= w[i] + b[i]) return false;
		}
	}
	return true;
}

inline void set (int x, int d, int flag) {

	if (flag > 0) {
		for (int i = 0; i < m; i++) {
			if (x == g[i][d])
				cnt[i]++;

			if (l[i][x] < r[i][x])
				sum[i]++;
			l[i][x]++;
		}
	} else {
		for (int i = 0; i < m; i++) {
			if (x == g[i][d])
				cnt[i]--;
			l[i][x]--;
			if (l[i][x] < r[i][x])
				sum[i]--;
		}
	}
}

bool dfs (int d) {
	if (d == p) {
		for (int i = 0; i < m; i++)
			if (cnt[i] != b[i] || sum[i] != w[i] + b[i]) return false;
		return true;
	}

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

		if (!judge(i, d)) continue;
		set(i, d, 1);

		ans[d] = i;
		if (dfs(d+1)) return true;

		set(i, d, -1);
	}
	return false;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();
		bool flag = dfs(0);

		if (flag) {
			printf("%d", ans[0]);
			for (int i = 1; i < p; i++)
				printf(" %d", ans[i]);
			printf("\n");
		} else 
			printf("You are cheating!\n");
	}
	return 0;
}