AtCoder Regular Contest #001 C : パズルのお手伝い
問題概要
一部が埋められた8クイーンがあるので残りを埋めて出力する問題。
acceptされたコード
import std.stdio; immutable W = 8; char[W][W+1] target; int[W] pos; int bit1, bit2, bit3; void init(){ for(int i=0; i<W; ++i){ scanf("%[^\n]%*c", target[i].ptr); } } bool dfs(int depth){ if(depth == W){ int cnt = 0; for(int i=0; i<W; ++i){ if(target[i][pos[i]] == 'Q'){ ++cnt; } } if( cnt == 3 ){ for(int i=0; i<W; ++i){ for(int j=0; j<W; ++j){ write(pos[i] == j ? 'Q' : '.'); } writeln; } return true; } return false; } int cannot = bit1 | bit2 | bit3; int t1 = bit1, t2 = bit2, t3 = bit3; for(int i=0; i<W; ++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; if(dfs(depth+1)){ return true; } } bit1 = t1; bit2 = t2; bit3 = t3; return false; } void solve(){ if(!dfs(0)){ writeln("No Answer"); } } void main(){ init; solve; }