AOJ1214 Walking Ant

問題リンク Walking Ant

• 概要

大きさH*Wのマップがあり、蟻と蟻の家と食べ物と石がある。蟻は単位時間に上下左右4マスに動くことができる。石のある場所は通れない。蟻が自分の家にたどり着くのにかかる最短時間を答えよ。
蟻はHPを持っており、その初期値と最大値は6である。蟻は単位時間毎に1HPずつ失い、0になると死んでしまう。
蟻は食べ物にたどり着くとそれを食べてHPを最大値まで回復できる。食べ物は大きいのでいくら食べても無くならない。
ただし、蟻は移動した結果HPが0になった瞬間に死んでしまうので、たとえそのマスが家でも到着したことにならず、食べ物でも回復することができない。家にたどり着くことができない場合は-1と答えよ。
W, H <= 8

• 解法

(座標, 残りHP)を頂点としたダイクストラもとい幅優先探索で解けます。

• ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Walking Ant
public class AOJ1214 {

	void run(){
		int[][] move = {{-1,0},{0,1},{1,0},{0,-1}};
		Scanner sc = new Scanner(System.in);
		for(;;){
			int w = sc.nextInt(), h = sc.nextInt();
			if((w|h)==0)break;
			int[][] map = new int[h][w];
			int si = -1, sj = -1;
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				map[i][j] = sc.nextInt();
				if(map[i][j]==2){
					si = i; sj = j;
					map[i][j] = 1;
				}
			}
			boolean[][][] u = new boolean[h][w][7];
			u[si][sj][6] = true;
			List<int[]> l = new ArrayList<int[]>();
			l.add(new int[]{si, sj, 6});
			int step = 0;
			int ans = -1;
			while(!l.isEmpty()){
				List<int[]> next = new ArrayList<int[]>();
				for(int[]a:l){
					int i = a[0], j = a[1], hp = a[2];
					if(map[i][j]==3){
						ans = step;
						next.clear();
						break;
					}
					if(hp<=1)continue;
					for(int k=0;k<4;k++){
						int ni = i+move[k][0];
						int nj = j+move[k][1];
						if(0<=ni&&ni<h&&0<=nj&&nj<w&&map[ni][nj]!=0){
							if(map[ni][nj]==4){
								if(u[ni][nj][6])continue;
								u[ni][nj][6] = true;
								next.add(new int[]{ni, nj, 6});
							}
							else{
								if(u[ni][nj][hp-1])continue;
								u[ni][nj][hp-1] = true;
								next.add(new int[]{ni, nj, hp-1});
							}
						}
					}
				}
				step++;
				l = next;
			}
			System.out.println(ans);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1214().run();
	}
}