AOJ1304 Infected Land - nanikakaのAOJ航海日誌

概要

N*Nのグリッドがある。グリッドのマスは
'.': 何もない
'#': 感染している
'@': 車
の3種類からなる。各ステップにつきグリッドの状態は次のように遷移する。
'#'マスは、周囲8マスにある感染マスの個数が2個が3個のとき次のステップも感染マスになる
'.'マスは、周囲8マスにある感染ますの個数がちょうど3個のとき、次のステップに感染マスになる
これら以外の場合、そのマスは'.'マスになる
'@'は1ステップにつき、周囲8マスのうち'.'にだけ移動することができる(移動せずにとどまることはできない)。'@'がいるマスは'#'に変化することがなくなる。ただし、あるマスについて周囲8マスにこの'@'マスがある場合、感染マスとしてカウントされる。
1ステップの最初に'@'を動かした後、グリッドの状態が変化する。
入力で与えられたグリッドにおいて、感染マスを0個にするための最小ステップを答えよ。不可能な場合は-1とせよ。
'@'マスは必ず1つだけあることが保証されている。
1 <= N <= 5

解法

幅優先探索です。
グリッドの状態は長さN*Nの文字列で表すことができます。また、'@'をある方向に動かした後得られるグリッドの状態は一意に決まります。
この方法だとグリッドの状態がだいたい、2^(N*N) * N*N くらいになって状態数の大きさが心配になるのですが、意外と通ってしまいました。ラッキーでしたね。

ソース

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

//Infected Land
public class AOJ1304 {

	class R{
		String s;
		int pos, c;
		public R(String s, int pos, int c) {
			this.s = s;
			this.pos = pos;
			this.c = c;
		}
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		int[][] d = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			char[] m = new char[n*n];
			int pos = 0, c = 0;;
			for(int i=0;i<n;i++){
				char[] t = sc.next().toCharArray();
				for(int j=0;j<n;j++){
					if(t[j]=='@')pos=i*n+j;
					if(t[j]=='#')c++;
					m[i*n+j]=t[j];
				}
			}
			Set<String> v = new HashSet<String>();
			List<R> l = new ArrayList<R>();
			l.add(new R(new String(m), pos, c));
			v.add(l.get(0).s);
			int res = -1, step = 0;
			while(!l.isEmpty()){
				List<R> next = new ArrayList<R>();
				for(R r:l){
					if(r.c==0){
						res = step; next.clear(); break;
					}
					int pi = r.pos/n, pj = r.pos%n;
					for(int k=0;k<8;k++){
						int ni = pi+d[k][0], nj = pj+d[k][1];
						char[] map = r.s.toCharArray();
						if(0<=ni&&ni<n&&0<=nj&&nj<n&&map[ni*n+nj]=='.'){
							map[ni*n+nj] = '@'; map[r.pos] = '.';
							int nc = 0;
							char[] nm = new char[n*n];
							for(int i=0;i<n;i++)for(int j=0;j<n;j++){
								if(map[i*n+j]=='@'){
									nm[i*n+j] = '@';
									continue;
								}
								int adj = 0;
								for(int x=0;x<8;x++){
									int xi = i+d[x][0], xj = j+d[x][1];
									if(0<=xi&&xi<n&&0<=xj&&xj<n&&map[xi*n+xj]!='.')adj++;
								}
								if(map[i*n+j]=='#'&&(adj==2||adj==3)){
									nm[i*n+j] = '#';
									nc++;
								}
								else if(map[i*n+j]=='.'&&adj==3){
									nm[i*n+j] = '#';
									nc++;
								}
								else nm[i*n+j] = '.';
							}
							R nr = new R(new String(nm), ni*n+nj, nc);
							if(!v.contains(nr.s)){
								v.add(nr.s); next.add(nr);
							}
						}
					}
				}
				step++;
				l = next;
			}
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new AOJ1304().run();
	}
}