Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-10

WalkingHome

| 16:29

問題文, SRM 222

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

学校から家に帰るまでに、最低何回道路を横断すればよいのか。道路は2つまでしか横断できないと勘違いしたために、1回落ちた。

150.00/500 (1 failed)

struct Johnny {
    int y, x, times;
    Johnny() { Johnny(0,0,0); }
    Johnny(const int y, const int x, const int times) :
        y(y), x(x), times(times) {}
};

class WalkingHome {
public:
    int fewestCrossings (vector <string> map) {
        const int H = map.size();
        const int W = map[0].size();
        Q = queue<Johnny>();
        visited = vector<vector<int> >(H, vector<int>(W, INT_MAX));
        int homeY=0, homeX=0;
        for (int y = 0; y < H; y++) {
            // cout << map[y]<< endl;
            for (int x = 0; x < W; x++) {
                if (map[y][x] == 'S') {
                    checkAndPush(Johnny(y,x,0));
                } else if (map[y][x] == 'H') {
                    homeY = y;
                    homeX = x;
                    map[y][x] = '.';
                }
            }
        }

        int result = INT_MAX;
        while (!Q.empty()) {
            Johnny j(Q.front());  Q.pop();
            if (j.y == homeY && j.x == homeX)
                result = min(result, j.times);
            const static int d[4][2] = {
                {1,0}, {-1,0}, {0,1}, {0,-1} };
            for (int i = 0; i < 4; i++) {
                const int ny = j.y + d[i][0];
                const int nx = j.x + d[i][1];
                int nnx, nny;
                if (!(0<=ny&&ny<H && 0<=nx&&nx<W)) continue;
                switch (map[ny][nx]) {
                    case '.':
                        checkAndPush(Johnny(ny,nx,j.times));
                        break;
                    case '|':
                        if (d[i][1] == 0) break;
                        nnx = nx + d[i][1];
                        while (0<=nnx&&nnx<W && map[ny][nnx] == '|')
                            nnx += d[i][1];
                        if (0<=nnx&&nnx<W && map[ny][nnx] == '.')
                            checkAndPush(Johnny(ny,nnx,j.times+1));
                        break;
                    case '-':
                        if (d[i][0] == 0) break;
                        nny = ny + d[i][0];
                        while (0<=nny&&nny<H && map[nny][nx] == '-')
                            nny += d[i][0];
                        if (0<=nny&&nny<H && map[nny][nx] == '.')
                            checkAndPush(Johnny(nny,nx,j.times+1));
                        break;
                }

            }
        }
        if (result == INT_MAX) return -1;
        else return result;
    }
private:
    queue<Johnny> Q;
    vector<vector<int> > visited;
    void checkAndPush(const Johnny& j) {
        if (j.times < visited[j.y][j.x]) {
            Q.push(j);
            visited[j.y][j.x] = j.times;
        }
    }
};