UVa-11085 : Back to the 8-Queens

問題概要

8クイーンの正しくないかもしれない配置が与えられる(ただし、各行はちがうことが保証されている)。正しい状態にするには最低幾つ動かす必要があるか求める問題。

解法

n=8だったらnクイーンの全探索は余裕を持って間に合うので解を全て生成して距離を求める。解は92個しかないので埋め込んでも良い。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int WIDTH = 8;
const int INF = 1<<29;

int pos[WIDTH], as[WIDTH];
int bit1, bit2, bit3;

bool init(){
	bool ok = true;
	for(int i=0; i<WIDTH; i++){
		ok &= scanf("%d", as+i)!=EOF;
		as[i]--;
	}

	return ok;
}

int dfs(int depth){
	if(depth == WIDTH){
		int cnt = 0;
		for(int i=0; i<WIDTH; i++){
			cnt += (as[i] == pos[i] ? 0 : 1);
		}
		return cnt;
	}

	int ret = INF;

	int cannot = bit1 | bit2 | bit3;
	int t1 = bit1, t2 = bit2, t3 = bit3;

	for(int i=0; i<WIDTH; i++)if(!((cannot>>i)&1) ){

		bit1 = t1 | (1<<i);
		bit2 = (t2<<1) | (1<<(i+1));
		bit3 = (t3>>1) | (i>0 ? 1<<(i-1) : 0);

		pos[depth] = i;
		ret = min(ret, dfs(depth+1));

	}

	bit1 = t1; bit2 = t2; bit3 = t3;

	return ret;
}

int solve(){
	bit1 = bit2 = bit3 = 0;
	return dfs(0);
}

int main(){
	int c = 0;
	while(init()){
		printf("Case %d: %d\n", ++c, solve());
	}

	return 0;
}