結果的は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); } }
まとめ
しょうもないミスで落としたのであまり大きな声では言えないが、なぜ今更こんな単なる総当たりを出したのだろう…。