TopCoder SRM 725 Div1 Easy: FiveRooks

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → 掲載されてないぽい (unrated だから？)

の盤面にルークがいくつか置かれている。

行の座標どうしが unique に、列の座標どうしが unique になるようにルークを つ選べ。

解説

なので、適当に全探索したら通ります。

ソースコード

class FiveRooks {
    public:
    const int S = 64;

    bool check(vector<string> board, int x) {
        int r = x / 8, c = x % 8;
        return board[r][c] == 'R';
    }

    void ins(set<int> &R, set<int> &C, vector<int> &ret, int x) {
        int r = x / 8, c = x % 8;
        R.insert(r);
        C.insert(c);
        ret.push_back(r);
        ret.push_back(c);
    }

    vector<int> find(vector<string> board) {
        rep(i,0,S) rep(j,i+1,S) rep(k,j+1,S) rep(l,k+1,S) rep(m,l+1,S) {
            bool ok = true;
            ok &= check(board, i);
            ok &= check(board, j);
            ok &= check(board, k);
            ok &= check(board, l);
            ok &= check(board, m);
            if(!ok) continue;

            vector<int> ret;
            set<int> R, C;
            ins(R, C, ret, i);
            ins(R, C, ret, j);
            ins(R, C, ret, k);
            ins(R, C, ret, l);
            ins(R, C, ret, m);

            if(R.size() != 5 || C.size() != 5) continue;
            return ret;
        }
        return vector<int>();
    }
};