Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-06

SmartWordToy

| 16:33

問題文, SRM 233

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

startからfinishに禁止された文字列を経由するためにかかる変換回数。BFSで解ける。時間制限がきつかった。

157.45/500 (1 failed)

class SmartWordToy {
public:
    int minPresses(string start, string finish, vector <string> forbid) {
        forbids.clear();
        for (int i = 0; i < forbid.size(); i++) {
            istringstream iss(forbid[i]);
            vector<string> token(WORD_LEN);
            for (int j = 0; j < WORD_LEN; j++)
                iss >> token[j];
            generateForbids(0, 0, token);
        }

        queue<pair<int,int> > Q;
        const int startCode = encode(start);
        const int finishCode = encode(finish);
        Q.push(make_pair(startCode, 0));
        set<int> checked;
        checked.insert(startCode);
        while (!Q.empty()) {
            pair<int,int> p = Q.front(); Q.pop();
            if (p.first == finishCode) return p.second;
            for (int i = 0; i < 4; i++) {
                for (int pad = -1; pad <= 1; pad += 2) {
                    int nextCode(next(p.first, pad, i));
                    if (checked.find(nextCode) == checked.end() && 
                            forbids.find(nextCode) == forbids.end()) {
                        checked.insert(nextCode);
                        Q.push(make_pair(nextCode, p.second+1));
                    }
                }
            }
        }
        return -1;
    }
private:
    set<int> forbids;
    const static int WORD_LEN = 4;
    void generateForbids(const int code, const int idx, const vector<string>& token) {
        if (idx == WORD_LEN) {
            forbids.insert(code);
            return;
        }
        for (int i = 0; i < token[idx].size(); i++)
            generateForbids(code*100+token[idx][i]-'a', idx+1, token);
    }
    int encode(const string& s) {
        int code = 0;
        for (int i = 0; i < WORD_LEN; i++)
            code = 100*code + s[i]-'a';
        return code;
    }
    int next(int code, const int pad, const int i) {
        const static int table[5] = {100*100*100*100,100*100*100,100*100,100,1};
        int v = code % table[i] / table[i+1];
        code -= v * table[i+1];
        v = (v+pad+26) % 26;
        code += v * table[i+1];
        return code;
    }
};