Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-11-03

MazeWanderingEasy

| 19:01

問題文, SRM 440

ねずみが最短でチーズに到達するために必要な決断の回数を求める。BFS。

387.83/500

struct State {
    int y, x, dec;
    State() {}
    State(int y, int x, int dec) : y(y), x(x), dec(dec) {}
};

class MazeWanderingEasy {
public:
    int decisions(vector <string> maze) {
        const int H = maze.size();
        const int W = maze[0].size();
        queue<State> Q;
        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++) {
                if (maze[y][x] == 'M') {
                    Q.push(State(y,x,0));
                    maze[y][x] = 'X';
                    break;
                }
                if (!Q.empty()) break;
            }
        while (!Q.empty()) {
            State s(Q.front()); Q.pop();
            vector<State> candid;
            for (int i = 0; i < 4; i++) {
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                const int ny = s.y + d[i][0];
                const int nx = s.x + d[i][1];
                if (0<=ny&&ny<H && 0<=nx&&nx<W && maze[ny][nx] != 'X') {
                    candid.push_back(State(ny,nx,s.dec));
                }
            }
            if (candid.size() >= 2)
                for (int i = 0; i < candid.size(); i++)
                    candid[i].dec++;
            for (int i = 0; i < candid.size(); i++) {
                const int y = candid[i].y;
                const int x = candid[i].x;
                if (maze[y][x] == '*')
                    return candid[i].dec;
                maze[y][x] = 'X';
                Q.push(candid[i]);
            }
        }
        return 0;
    }
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20091103