Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-08

Orchard

| 20:44

SRM447 (DIV2)の結果は、300と500を通すことができ、Ratingは 1063 -> 1099 と上がった。両問題とももう少し速くサブミットできたのだが、コードを何度も確認していたため、しょぼいポイントになった。慎重になりすぎた。

問題文

幅優先探索(BFS)で解ける問題。実装に手間取った。

328.06/900 - 01:03:38

enum INDEX { Y_IDX=0, X_IDX=1, DIS_IDX=2};

class Orchard {
    public:
        vector <int> nextTree(vector <string> orchard) {
            const int size = orchard.size();
            vector<int> best = vector<int>(2);
            int longest = -1;
            for (int y = 0; y < size; y++) 
                for (int x = 0; x < size; x++)
                    if (orchard[y][x] == '-') {
                        set<vector<int> > visited;
                        queue<vector<int> > Q;
                        vector<int> tmp(3);
                        tmp[Y_IDX]=y; tmp[X_IDX]=x; tmp[DIS_IDX] = 0;
                        Q.push(tmp);
                        while (!Q.empty()) {
                            vector<int> v = Q.front(); Q.pop();
                            if (v[Y_IDX] < 0 || v[Y_IDX] >= size ||
                                    v[X_IDX] < 0 || v[X_IDX] >= size ||
                                    orchard[v[Y_IDX]][v[X_IDX]] == 'T') {
                                if (v[DIS_IDX] > longest) {
                                    longest = v[DIS_IDX];
                                    best[Y_IDX] = y + 1;
                                    best[X_IDX] = x + 1;
                                }
                                break;
                            }
                            tmp = vector<int>(v.begin(), v.begin()+2);
                            if (visited.find(tmp) != visited.end()) continue;
                            visited.insert(tmp);
                            vector<int> newV(3); 
                            newV[DIS_IDX] = v[DIS_IDX] + 1;
                            newV[Y_IDX]=v[Y_IDX]+1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]-1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]+1; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]-1; Q.push(newV);
                        }
                    }
            return best;
        }
};

ewnfzgewnfzg2011/02/28 00:358HHlV6 <a href="http://nfypkepkeych.com/">nfypkepkeych</a>, [url=http://azgnisbcmhab.com/]azgnisbcmhab[/url], [link=http://jedmlehhrowo.com/]jedmlehhrowo[/link], http://pqvizwthqdkq.com/