読者です 読者をやめる 読者になる 読者になる

AOJ 2538 Stack Maze

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2538
かなりハマりました……。AOJ-ICPCで500くらいで面白そうな問題を探していて、グリッドグラフ探索問題好きだし面白そうだな~と思って手を出したのですが、少し僕にはオーバーだったかも。
 主人公は洞窟(グリッドグラフ)を(1, 1)から(W, H)まで行きます。右か下にしか進めません。その途中でアイテムa,b,...,zを拾い、穴A,B,...,Zにはめていきます。このとき、主人公のバッグはスタックになっており、最後に入れたものしか取り出せません。さて最大何個入れられるか、というのが問題。
 普通に探索を書くと、アイテムの数^2 * マス目の数^2とかになってオワコンです。実際に書きましたが全くダメでした。ではどうするのかというと、メモ化再帰を使います。とりあえず典型力に頼ろうということで、輪番停電計画と同じように区間を持つテーブルを考えます。
 dp[i][j][k][l] := (j, i)(左上)から(l, k)(右下)の区間での最大値(閉区間)
とします。以下、左上の点をa, 右下の点をbとします。
 まず、aがアイテム以外のとき。これは次に移動したところからの区間と同じでしょう。右、下に移動して最大値を取ります。
 次に、aがアイテムのとき。このとき、aのアイテムに対応する穴を列挙し、その穴が区間内にあれば再帰します。このとき、dfs(aから1マス移動した点、bから1マス移動した点)+ dfs(穴、b)+ 1のようにしないと、穴をダブって数えてしまう事になります。また、到達できない点については、aかbの片方が壁だったらはじく、というだけで問題ありません。
 やっかいなのがaAのようなケースで、dfs(aから1マス移動した点、bから1マス移動した点)がすべて区間が交差したものになってしまいます(区間が交差している時に0を返すようにすると到達できないケースを一部弾けなくなり、間違える)。このときだけ特別に例外処理を書きます。

struct Point{
    int x, y;
    Point() {x = y = -1;}
    Point(int x, int y): x(x), y(y) {}
    bool operator== (const Point& p) const { return x == p.x && y == p.y; }
    bool operator< (const Point& p) const { return x < p.x || y < p.y; }
    const Point operator+ (const Point& p) const { return Point(x + p.x, y + p.y);}
};
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int H, W;
vector<string> fld;
int dp[51][51][51][51];
vector<Point> holes[26];

bool range_out(Point a){
    return a < Point(0, 0) || Point(W - 1, H - 1) < a ;
}
bool is_Wall(Point a){
    return fld[a.y][a.x] == '#';
}
int dfs(Point a, Point b){
    int& res = dp[a.y][a.x][b.y][b.x];
    if(res != -1) return res;
    if(b.x + b.y - a.x - a.y == -1) return res = 0;
    res = -INF;
    if(range_out(a) || range_out(b) || is_Wall(a) || is_Wall(b) || b < a) return res;
    if(a == b) return res = 0;
    if('a' <= fld[a.y][a.x] && fld[a.y][a.x] <= 'z'){
        int k = fld[a.y][a.x] - 'a';
        for(Point hole : holes[k]){
            if(hole < a || b < hole) continue;
            rep(i, 2) REP(j, 2, 4){
                Point nx1 = a + Point(dx[i], dy[i]), nx2 = hole + Point(dx[j], dy[j]);
                res = max(res, dfs(nx1, nx2) + dfs(hole, b) + 1);
            }
        }
    }
    rep(i, 2)
      res = max(res, dfs(a + Point(dx[i], dy[i]), b));
    return res;
}
bool can_reach[51][51];
bool bfs(){
    memset(can_reach, 0, sizeof(can_reach));
    queue<Point> que;
    que.push(Point(0, 0));
    can_reach[0][0] = true;
    while(!que.empty()){
        Point now = que.front(); que.pop();
        rep(i, 2){
            int nx = now.x + dx[i], ny = now.y + dy[i];
            if(W <= nx || H <= ny || fld[ny][nx] == '#' || can_reach[ny][nx])
              continue;
            can_reach[ny][nx] = true;
            que.push(Point(nx, ny));
        }
    }
    return can_reach[H - 1][W - 1];
}
void find_hole(){
    rep(i, 26) holes[i].clear();
    rep(i, H) rep(j, W)
      if('A' <= fld[i][j] && fld[i][j] <= 'Z')
        holes[fld[i][j] - 'A'].push_back(Point(j, i));
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ifstream ifs("2538_in1.txt");
    while(cin >> H >> W && H){
        fld = vector<string>(H);
        rep(i, H) cin >> fld[i];
        if(!bfs()){
            cout << "-1" << endl;
            continue;
        }
        find_hole();
        memset(dp, -1, sizeof(dp));
        cout << max(0, dfs(Point(0, 0), Point(W - 1, H - 1))) << endl;
    }
}

 そもそも探索の問題だと思って書き始めたり、例外処理でハマってしまったりしてきつかったですが、通せて良かったです。初めてあおいちゃんにユーザーIDをツイートしてもらえました。