Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-23

PizzaDelivery

| 07:29

問題文, SRM 451

2人の配達人を使って、ピザを配達し終えるのにかかる最短時間を求める。

解くのに2時間強かかった。しょうもないバグにより3回、時間制限により1回、システムテストで落とされた。解法はBFS+Brute Forceなので割と単純だが、異常に調子が良い時でないと本番の時間内にバグなしで解ける気がしない。

300.00/1000 (4-failed)

const static int INFTY = INT_MAX/2;

class PizzaDelivery {
    public:
        int deliverAll(vector <string> terrain) {
            const int H = terrain.size();
            const int W = terrain[0].size();
            vector<pair<int,int> > piza;
            pair<int,int> r;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (terrain[y][x] == 'X') {
                        r = make_pair(y, x);
                    } else if (terrain[y][x] == '$') {
                        piza.push_back(make_pair(y,x));
                    }
                }

            int D[100];
            int T[100][100];
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                    T[y][x] = INFTY;
            T[r.first][r.second] = 0;
            queue<pair<int,int> > Q;
            Q.push(r);
            while (!Q.empty()) {
                pair<int,int> a = Q.front(); Q.pop();
                const int y = a.first, x = a.second;
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                for (int i = 0; i < 4; i++) {
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                        if (!isdigit(terrain[ny][nx]) || !isdigit(terrain[y][x])) {
                            if (T[y][x]+2 < T[ny][nx]) {
                                T[ny][nx] = T[y][x] + 2;
                                Q.push(make_pair(ny, nx));
                            }
                            continue;
                        }
                        if (abs(terrain[ny][nx]-terrain[y][x]) == 0 && 
                                T[y][x]+1 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 1;
                            Q.push(make_pair(ny, nx));
                        } else if (abs(terrain[ny][nx]-terrain[y][x]) == 1 && 
                                T[y][x]+3 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 3;
                            Q.push(make_pair(ny, nx));
                        }
                    }
                }
            }
            for (int i = 0; i < piza.size(); i++) {
                D[i] = T[piza[i].first][piza[i].second];
                if (D[i] == INFTY) return -1;
            }

            int minTime = INFTY;
            for (int i = 0; i < 1<<(piza.size()-1); i++) {
                bitset<20> pat(i);
                vector<int> vboy1, vboy2;
                for (int j = 0; j < piza.size(); j++) {
                    if (pat[j]) vboy1.push_back(D[j]);
                    else        vboy2.push_back(D[j]);
                }
                int boy1=0, boy2=0;
                if (vboy1.size() > 0)
                    boy1 = 2*accumulate(vboy1.begin(), vboy1.end(), 0) 
                        - *max_element(vboy1.begin(), vboy1.end());
                if (vboy2.size() > 0)
                    boy2 = 2*accumulate(vboy2.begin(), vboy2.end(), 0) 
                        - *max_element(vboy2.begin(), vboy2.end());
                //cout << pat << " " << boy1 << " " << boy2 << endl;
                minTime = min(minTime, max(boy1, boy2));
            }
            return minTime;
        }
};

nphuuejznphuuejz2011/02/28 17:01PX5gMr <a href="http://thxvtmuhvzkh.com/">thxvtmuhvzkh</a>, [url=http://aegsueyzfdwj.com/]aegsueyzfdwj[/url], [link=http://juwwqktqnkxe.com/]juwwqktqnkxe[/link], http://fuvdtrdrrxop.com/