AOJ2146 Ninja Legend
問題リンク Ninja Legend
- 概要
H*Wの大きさのマップがある。マップは
'%': 出入り口
'#': 壁
'.': 床
'^': 落とし穴
'*': 宝
で構成されている。忍者は出入り口から侵入し、出入り口から脱出する。
忍者は1単位時間に1マス進むことができる。落とし穴に進入することはできない。
忍者にはノーマルモードとダッシュモードの2つの状態がある。初期状態はノーマルモードである。モードの違いによって落とし穴を避けるためのアクションが変わる。
ノーマルモード：
落とし穴1つ分のジャンプができる
ダッシュモード：
落とし穴1つ、または2つ分のジャンプができる
現在地点、着地点含めてそのすぐ横に壁が連続してつながっている場合、壁を走ることにより最大で落とし穴4つ分のジャンプができる
ノーマルモードからダッシュモードへ移行する条件は、同じ方向に2マス進んだときである。向いている方向が変わったり、壁走りのアクションを起こした場合、ダッシュモードは終了してノーマルモードになる。
忍者が宝のマスに来た場合、宝を取ることができる。宝を無視してもよい。ただし、宝を取得した場合、ダッシュモードはノーマルモードへ移行する。
忍者が出入り口から出発して、出入り口に戻るとき、得ることのできる宝の最大個数を答えよ。更に、それにかかる最短時間を答えよ。宝を1つも手に入れられないときは双方0とせよ。
以下のことが保証されている
マップの周囲は'#'で囲まれている
宝は最大で15個である
出入り口のマスは必ず1つだけある
3 <= H <= 60
3 <= W <= 80
- 解法
問題文補足
問題文を読んだだけでは、ノーマルモードからダッシュモードへ移行する条件が曖昧な感じがしませんでしたか？(自分はそうでした)。とりあえず、次のような理解でよさそうです。
「2マス進んだ」というのは、今いる地点(ノーマル状態)からある方向Dへ'.'が2マス続いているとき、その2マス先の'.'において方向Dへのダッシュ状態になる、ということです。例えば、(アルファベットは'.'マスだと思ってください)
%.A^^B.
##^####
##^####
##C####
というマップだったら、Aに到達した時点で右方向へダッシュ状態になります。ダッシュ状態なので2つ分の落とし穴が飛び越せてBへ進めます。ただし、方角が変わるとダッシュ状態がキャンセルされるので、Cへは進めません。
次の場合はどうでしょう
B^^A^%.^C^^D
%から左へジャンプしてAへ来た時、左へ2マス進んだことになりますが'.'が連続しているわけではないのでダッシュ状態にはなりません。よってBへジャンプできません。
%から右へ行く時、1度ジャンプを挟んでCへ進めます。右方向へ進み続けて2マス目の'.'を踏んだわけですが、連続しているわけではないのでやはりダッシュ状態にはなりません。よってDへも進めません。
次の場合はどうでしょう
%.^.A^^B
Aの手前に'.'があるので、'.'が連続したことになり、Aでダッシュ状態になってBへ進め・・・ません。
%.^...^^B
これならBへ進めます。
補足おしまい
この問題は大きく2つの部分に分かれます。宝マス、出入り口マスの全頂点間の最短距離を求める部分と、巡回セールスマン問題を解いて宝を集めるための最短距離を求める部分です。
全頂点間の最短距離は、頂点の数の回数だけダイクストラを適用して求めます。ダイクストラのグラフの頂点は[座標][方向][ダッシュモードか否か]の探索空間となります。
これが求まったらTSPを解く要領で、宝を集めるための最短時間を求めます。
dp[S][last]: 集めた宝の状態S, 最後に訪れた頂点last
というDP表をメモ化再帰で埋めました。
この問題は、ダイクストラしたりTSPしたりで厄介なのですが、ここからが更に厄介です。普通に書いたプログラムだとTLEに引っ掛かります。最適化の時間です。
ダイクストラ:
始点i以外の全てのマスについて最短距離が求まったら探索を終了しましょう。若干早くなります。
最短距離をしまう配列を逐一確保するのはやめましょう。配列の大きさは4800*4*2 ≒ 40000程度なのですが、これを何度もnew するとえらい量の時間を食います。プログラムの最初で最大サイズをnewして、以降は初期化しながら使いましょう。この工夫が一番効果的でした。
TSP:
同じ要領で、DP表もnew するのは一度だけにしましょう。2^16 * 16の大きさが最大です。
あとは、状態Sを降順で回しながらやると早いかなと思います。気持ち改善されます。
これでようやく通ります。
- ソース
import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; //Ninja Legend public class AOJ2146 { int h, w, N, INF = 1<<29; char[][] map; int[][] d = {{-1,0},{0,1},{1,0},{0,-1}}, adj, id, dp; int get(int S, int last){ if(dp[S][last]!=-1)return dp[S][last]; int res = INF; for(int i=0;i<N;i++){ if(i==last||((S>>i)&1)==0||adj[i][last]==INF)continue; int ns = S-(1<<last); res = Math.min(res, adj[i][last]+get(ns, i)); } return dp[S][last] = res; } boolean dash(int i, int j, int k, int len){ if(map[i][j]!='.')return false; int gi = i+len*d[k][0], gj = j+len*d[k][1]; if(!(0<=gi&&gi<h&&0<=gj&&gj<w)||map[gi][gj]!='.')return false; int pi = i, pj = j; for(int x=0;x<len;x++){ pi += d[k][0]; pj += d[k][1]; if(map[pi][pj]=='#')return false; } int i1 = i+d[(k+1)%4][0], j1 = j+d[(k+1)%4][1], i2 = i+d[(k+3)%4][0], j2 = j+d[(k+3)%4][1]; boolean f1 = true, f2 = true; for(int x=0;x<=len;x++){ if(map[i1][j1]!='#')f1 = false; if(map[i2][j2]!='#')f2 = false; i1 += d[k][0]; j1 += d[k][1]; i2 += d[k][0]; j2 += d[k][1]; } return f1|f2; } boolean jump(int i, int j, int k, int len){ if(map[i][j]!='.')return false; int gi = i+len*d[k][0], gj = j+len*d[k][1]; if(!(0<=gi&&gi<h&&0<=gj&&gj<w)||map[gi][gj]!='.')return false; for(int x=1;x<len;x++){ int ni = i+x*d[k][0], nj = j+x*d[k][1]; if(map[ni][nj]!='^')return false; } return true; } int[][][][] dist; void dijkstra(int i, int j){ int ID = id[i][j]; int mask = 1<<ID; adj[ID][ID] = 0; for(int I=0;I<h;I++)for(int J=0;J<w;J++)for(int k=0;k<4;k++)for(int c=0;c<2;c++)dist[I][J][k][c] = INF; PriorityQueue<int[]> q = new PriorityQueue<int[]>(h*w, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return dist[a[0]][a[1]][a[2]][a[3]]-dist[b[0]][b[1]][b[2]][b[3]]; } }); for(int k=0;k<4;k++){ dist[i][j][k][0] = 0; q.add(new int[]{i, j, k, 0}); } while(!q.isEmpty()){ int[] a = q.poll(); int pi = a[0], pj = a[1], dir = a[2], pc = a[3], cost = dist[pi][pj][dir][pc]; if(id[pi][pj]!=-1){ mask |= 1<<id[pi][pj]; adj[ID][id[pi][pj]] = Math.min(adj[ID][id[pi][pj]], cost); } if(mask==(1<<(N+1))-1)break; //dash mode if(pc==1){ //run along wall for(int len=2;len<=5;len++){ if(dash(pi, pj, dir, len)){ int w = cost+len; if(w < dist[pi+len*d[dir][0]][pj+len*d[dir][1]][dir][0]){ dist[pi+len*d[dir][0]][pj+len*d[dir][1]][dir][0] = w; q.add(new int[]{pi+len*d[dir][0], pj+len*d[dir][1], dir, 0}); } } } //jump just two falls if(jump(pi, pj, dir, 3)){ int w = cost+3; if(w < dist[pi+3*d[dir][0]][pj+3*d[dir][1]][dir][1]){ dist[pi+3*d[dir][0]][pj+3*d[dir][1]][dir][1] = w; q.add(new int[]{pi+3*d[dir][0], pj+3*d[dir][1], dir, 1}); } } } for(int k=0;k<4;k++){ if(k!=dir){ if(cost < dist[pi][pj][k][0]){ dist[pi][pj][k][0] = cost; q.add(new int[]{pi, pj, k, 0}); } continue; } int ni = pi+d[k][0], nj = pj+d[k][1]; boolean f = false; if(map[ni][nj]=='.'){ f = true; int w = cost + 1; int nc = pc; if(w < dist[ni][nj][k][nc]){ dist[ni][nj][k][nc] = w; q.add(new int[]{ni, nj, k, nc}); } } ni += d[k][0]; nj += d[k][1]; if(jump(pi, pj, k, 2)){ int w = cost+2; int nc = pc; if(w < dist[ni][nj][k][nc]){ dist[ni][nj][k][nc] = w; q.add(new int[]{ni, nj, k, nc}); } } if(f&&0<=ni&&ni<h&&0<=nj&&nj<w&&map[ni][nj]=='.'){ int w = cost+2; int nc = 1; if(w < dist[ni][nj][k][nc]){ dist[ni][nj][k][nc] = w; q.add(new int[]{ni, nj, k, nc}); } } } } } void run(){ Scanner sc = new Scanner(System.in); dp = new int[1<<16][16]; for(;;){ h = sc.nextInt(); w = sc.nextInt(); if((h|w)==0)break; map = new char[h][w]; id = new int[h][w]; for(int[]a:id)Arrays.fill(a, -1); N = 0; int si = 0, sj = 0; List<int[]> mark = new ArrayList<int[]>(); for(int i=0;i<h;i++){ map[i] = sc.next().toCharArray(); for(int j=0;j<w;j++){ if(map[i][j]=='%'){ map[i][j] = '.'; si = i; sj = j; mark.add(new int[]{i, j}); } if(map[i][j]=='*'){ map[i][j] = '.'; id[i][j] = N++; mark.add(new int[]{i, j}); } } } id[si][sj] = N; adj = new int[N+1][N+1]; for(int[]a:adj)Arrays.fill(a, INF); dist = new int[h][w][4][2]; for(int[]a:mark)dijkstra(a[0], a[1]); for(int[]a:dp)Arrays.fill(a, -1); for(int i=0;i<=N;i++)dp[(1<<N)|(1<<i)][i] = adj[N][i]; int max = 0, min = INF; for(int i=(1<<N)-1;i>=0;i--){ int c = 0; for(int j=0;j<N;j++)if(((i>>j)&1)>0)c++; if(c<max)continue; int r = INF; for(int j=0;j<N;j++){ if(((i>>j)&1)==0||adj[j][N]==INF)continue; r = Math.min(r, get(i+(1<<N), j) + adj[j][N]); } if(r==INF)continue; if(max<c){ max = c; min = r; } else if(max==c&&r<min)min = r; } if(max==0)min = 0; System.out.println(max+" "+min); } } public static void main(String[] args) { new AOJ2146().run(); } }
