Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-06

CaptureThemAll

| 19:09

問題文, SRM 207

Algorithm Tutorials -- How to Find a Solutionから。

Knightだけで、RookとQueenをとるのに最低何ステップかかるか。BFSで解ける。どのように実装すればよいのかで迷った。1回目と2回目に出したときは、setを使って同じ条件の時にはもう調べないようにしなかったために、queueの許容量を超えてしまい、例外が発生して落ちた(例外が発生しなくても時間制限に引っかかったと思うが)。

300.00/1000 (2 failed)

struct State {
    const static int ROOK_VAL = 1;
    const static int QUEEN_VAL = 10;
    const static int BOTH_VAL = ROOK_VAL+QUEEN_VAL;
    pair<int,int> p;
    int step, val;
    State() {}
    State(const pair<int,int> p) : p(p) {
        step = 0;
        val = 0;
    }
    State(const pair<int,int> p, const int step) : p(p), step(step) {
        val = 0;
    }
};
bool operator< (const State& a, const State& b) {
    if (a.step < b.step) {
        return true;
    } else if (a.step > b.step) {
        return false;
    } else {
        if (a.val > b.val) {
            return true;
        } else if (a.val < b.val) {
            return false;
        } else {
            return a.p < b.p;
        }
    }
}

class CaptureThemAll {
public:
    int fastKnight(string knight, string rook, string queen) {
        const pair<int,int> rPos = getPos(rook);
        const pair<int,int> qPos = getPos(queen);
        queue<State> Q;
        Q.push(State(getPos(knight)));
        set<State> checked;
        checked.insert(Q.front());
        while (!Q.empty()) {
            State k = Q.front(); Q.pop();
            if (k.val == State::BOTH_VAL) return k.step;
            for (int dy = -2; dy <= 2; dy++) {
                for (int dx = -2; dx <= 2; dx++) {
                    if (dy*dy+dx*dx != 5) continue;
                    const int ny = k.p.first + dy;
                    const int nx = k.p.second + dx;
                    if (0<=ny&&ny<BOARD_SZ && 0<=nx&&nx<BOARD_SZ) {
                        State next(make_pair(ny,nx), k.step+1);
                        if (k.val%10 == 1 || next.p == rPos) 
                            next.val += State::ROOK_VAL;
                        if (k.val/10 == 1 || next.p == qPos)
                            next.val += State::QUEEN_VAL;
                        if (checked.find(next) == checked.end()) {
                            Q.push(next);
                            checked.insert(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
private:
    const static int BOARD_SZ = 8;
    pair<int,int> getPos(const string& s) {
        return make_pair(s[1]-'1', s[0]-'a');
    }
};