SRM725 Lv1 : FiveRooks
作成日：2017.12.11
最終更新日：2017.12.11
問題概要
$8 \times 8$の大きさのチェス盤の半数を超えるマスにルークが置かれている。
これらのルークのうち5つを選ぶ。
ある行またはある列に選んだルークが2つ以上あってはならない。
この条件を満たすルークの選び方は必ず存在する。そのうちの1つを求めよ。
制約
$board[r][c]$が$R$の時、$r$行$c$列にルークが存在する($0 \leq r,c \leq 7$)
考え方
制約が小さいので全探索ができる。
具体的には、行$r$に列$c_r$を割り当てた後$board[r][c_r]$のうち5つ以上が$R$であれば、そのうちの5つを選べば良い。
列の割り当て方は$8!$通りあるが、これを列挙するのはnext_permutationを用いれば容易に行える。
ソースコード
マクロ等はこちら
class FiveRooks {
public:
vector<int> find(vector<string> board) {
vector<int> P = {0,1,2,3,4,5,6,7};
do {
vector<int> ans;
int c = 0;
repp(i,0,8) if(board[i][P[i]]=='R'){
ans.push_back(i);
ans.push_back(P[i]);
++c;
if(c==5) return ans;
}
} while(next_permutation(P.begin(),P.end()));
return vector<int>();
}
};解法まとめ
行に割り当てる列をnext_permutationを用いてすべて試す。(4-14行)
SRM725の他の問題 Lv2 Lv3