kmjp's blog

競技プログラミング参加記です

TopCoder SRM 725 Div1 Easy FiveRooks

結果的はUnratedでよかったけど何なんだこれ。
(URL掲載待ち)

問題

チェスの盤面上にルークの駒がいくつか置かれる。
このうち5個を選び、互いの移動範囲に互いの駒が来ないようにせよ。

解法

制限が緩いので色々な解き方がある。
bitdpとかnext_permutationとか。

以下の解は、1行ずつルークを置く列を総当たりして、問題ないケースを探している。

class FiveRooks {
	public:
	int B[8][8];
	
	vector<int> dfs(int y,vector<int>& V,int mask) {
		if(V.size()==10) return V;
		if(y==8) {
			return vector<int>();
		}
		
		vector<int> R;
		R=dfs(y+1,V,mask);
		if(R.size()) return R;
		
		int x;
		FOR(x,8) if(B[y][x] && (mask&(1<<x))==0) {
			V.push_back(y);
			V.push_back(x);
			R=dfs(y+1,V,mask|(1<<x));
			V.pop_back();
			V.pop_back();
			if(R.size()) return R;
		}
		return R;
		
	}
	
	vector <int> find(vector <string> board) {
		int mask[8]={};
		int y,x;
		FOR(y,8) {
			FOR(x,8) B[y][x]=board[y][x]=='R';
		}
		vector<int> V;
		return dfs(0,V,0);
		
	}
}

まとめ

しょうもないミスで落としたのであまり大きな声では言えないが、なぜ今更こんな単なる総当たりを出したのだろう…。