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をツイートしてもらえました。