AOJ2089 Mysterious Dungeons - nanikakaのAOJ航海日誌

概要

W*Hのマップがある。人('@')と出口('>')が1つずつある。人は隣接する4マスへ移動できる。
アルファベット大文字は岩を表す。岩は消えている状態と消えていない状態の2つの状態を持つ。消えている状態ならば人はこのマスを通ることができる。
アルファベット小文字はパネルを表し、人がこのパネルを踏むとこの文字に対応する岩の状態を変化させる。
全ての岩の初期状態は消えていない状態である。人が出口へたどり着くための最短時間を答えよ。たどり着けない場合は-1とせよ。
マップの周囲は壁('#')で覆われていることが保証されている。また、岩の種類は高々8種類、パネルの種類も高々8種類までである。
3 <= W, H <= 30

解法

幅優先探索です。岩の種類は8種類までしかないので、岩の状態を1つの整数で表すことができます。つまり、探索空間は[W][H][岩の状態]となります。
プログラムを書きやすくするためにマップに下処理を加えています。
まず、'@'と'>'はその座標を覚えたうえで、'.'に置き換えます。
対応する岩がないパネルは意味がないので、これも'.'に置き換えます。
岩には適当に0からの番号を割り当てます('A'には0, 'C'に1 etc...)。
あとはこれでBFSをやるだけです。

ソース

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

//Mysterious Dungeons
public class AOJ2089 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
		for(;;){
			int w = sc.nextInt(), h = sc.nextInt();
			if((w|h)==0)break;
			char[][] m = new char[h][];
			int si = 0, sj = 0, gi = 0, gj = 0;
			boolean[] u = new boolean[26];
			for(int i=0;i<h;i++){
				m[i]=sc.next().toCharArray();
				for(int j=0;j<w;j++){
					if(m[i][j]=='@'){
						si = i; sj = j; m[i][j] = '.';
					}
					if(m[i][j]=='<'){
						gi = i; gj = j; m[i][j] = '.';
					}
					if(Character.isUpperCase(m[i][j]))u[m[i][j]-'A']=true;
				}
			}
			for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(Character.isLowerCase(m[i][j])&&!u[m[i][j]-'a'])m[i][j]='.';
			int id = 0;
			int[] b = new int[26];
			for(int i=0;i<26;i++)if(u[i])b[i]=id++;
			boolean[][][] v = new boolean[h][w][256];
			int step = 0, res = -1;
			List<int[]> l = new ArrayList<int[]>();
			l.add(new int[]{si, sj, 0});
			v[si][sj][0] = true;
			while(!l.isEmpty()){
				List<int[]> next = new ArrayList<int[]>();
				for(int[]a:l){
					int i = a[0], j = a[1], s = a[2];
					if(i==gi&&j==gj){
						res = step; next.clear(); break;
					}
					for(int k=0;k<4;k++){
						int ni = i+d[k][0], nj = j+d[k][1], ns = s;
						if(m[ni][nj]=='#')continue;
						if(Character.isUpperCase(m[ni][nj])){
							if(((s>>b[m[ni][nj]-'A'])&1)==0)continue;
						}
						else if(Character.isLowerCase(m[ni][nj])){
							if(((s>>b[m[ni][nj]-'a'])&1)==0)ns+=1<<b[m[ni][nj]-'a'];
							else ns-=1<<b[m[ni][nj]-'a'];
						}
						if(!v[ni][nj][ns]){
							v[ni][nj][ns] = true; next.add(new int[]{ni, nj, ns});
						}
					}
				}
				step++;
				l = next;
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2089().run();
	}
}