GCJ 2015 Round 2 A. Pegman

2015/06/20 (Sat) GCJ アドホック

問題

問題文

$R \times C$ のグリッドがある．各マスは空白か上下左右の矢印が書かれている． ペグマンはどこかのマスに降り立ち，もしそこが空白だった場合はそこで静止する． 矢印だった場合は矢印の向きに進みだし，別の矢印にぶつかったらその方向に変えて進むということを繰り返す． ただし，グリッドの外に出たら負けである．

あなたは，矢印をいくつか選んで好きな向きに変えられる． ペグマンがどこに降りても場外に出ないようにするために，変えなければいけない矢印の数の最小値を求めなさい． 不可能な場合は IMPOSSIBLE と出力しなさい．

方針

外に向かっている矢印を見つけたら，そこから $4$ 方向を見て別の矢印を探し，あったらそっちに向ける． それを繰り返すと無限ループが作れ，グリッドの外に出なくなる． どの向きにも矢印がないものがあったら IMPOSSIBLE を返す．

実装

int solve(int const R, int const C, vector<string> const g){
    int di[256],dj[256];
    di[(int)'^'] = -1;
    di[(int)'v'] = +1;
    di[(int)'>'] = 0;
    di[(int)'<'] = 0;

    dj[(int)'^'] = 0;
    dj[(int)'v'] = 0;
    dj[(int)'>'] = +1;
    dj[(int)'<'] = -1;
    auto inside = [&](int i, int j){
        return 0 <= i && i < R && 0 <= j && j < C;
    };

    int ans = 0;
    rep(i,R){
        rep(j,C){
            if(g[i][j] == '.') continue;
            char dir = g[i][j];
            int ci, cj;
            ci = i+di[(int)dir], cj = j+dj[(int)dir];

            while(inside(ci,cj) && g[ci][cj]=='.'){
                ci += di[(int)dir], cj += dj[(int)dir];
            }
            if(inside(ci,cj)) continue;
            bool ok = false;
            for(char ndir : {'>','<','^','v'}){
                if(ndir == dir) continue;
                ci = i+di[(int)ndir], cj = j+dj[(int)ndir];
                while(inside(ci,cj) && g[ci][cj]=='.'){
                    ci += di[(int)ndir], cj += dj[(int)ndir];
                }
                if(inside(ci,cj)) ok = true;
            }
            //dump(i,j,ci,cj,ok);
            if(ok) ans++;
            else return -1;
        }
    }
    return ans;
}

signed main(){
    int t;
    cin >> t;
    rep(i,t){
        int R,C;
        cin >> R >> C;
        vector<string> g(R);
        rep(i,R) cin >> g[i];
        int ans = solve(R,C,g);
        if(ans != -1) printf("Case #%d: %d\n", signed(i+1), signed(ans));
        else printf("Case #%d: %s\n", signed(i+1), "IMPOSSIBLE");
    }
}