AOJ1243 Weather Forecast - nanikakaのAOJ航海日誌

概要

4*4の大きさの国があり、16個の町がある。そして2*2の大きさの雲がある。雲の下は必ず雨でそれ以外は晴れている。雲は国の国境をまたぐような位置にいることはできない。雲は最初に5,6,10,11の町の上部を覆う位置にいる。
雲は1日のはじめに上下左右に最大2マスまで動くか、その場にとどまることができる。斜めに動くことはできない。
N日間の各町の行事予定が与えられ、普通の日か祭りの日かを表す。
祭りの日に雨を降らせてはならない。また、7日間以上連続で雨が降らない町があってはならない。
これら2つの条件を満たすように雲を動かすことができるかを判定せよ。
N <= 365

解法

まず各町を0〜15で表すことにします。
雲がいることができるパターンは9通りで、その位置を0〜8で表します。cover[i][4]という配列に、雲が i にいるときに雨が降っている町を覚えさせておきます。また、move[i][5]に雲 i が次の日に動くことができる位置を入れておきます。
方針はメモ化探索です。
x日に雲がposにいて、そのとき、各町について残り何日で雨が降らなければならないか、という情報を持ってメモ化します。
3番目の情報については0〜6の範囲の数字が16個並ぶことになるのでlong型の整数として表すことができます。つまり、Set[x][pos]に既に探索した町の状態をメモしておくわけです。
後は、moveとcoverを使って探索をしていくだけです。
町の状態は7^16あるのでメモリが足りるか不安だったのですが、何とか大丈夫でした。

ソース

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Weather Forecast
public class AOJ1243 {

	int[][] cover = {
			{0,1,4,5},
			{1,2,5,6},
			{2,3,6,7},
			{4,5,8,9},
			{5,6,9,10},
			{6,7,10,11},
			{8,9,12,13},
			{9,10,13,14},
			{10,11,14,15}
	};
	int move[][] = {
			{0,1,2,3,6},
			{0,1,2,4,7},
			{0,1,2,5,8},
			{0,3,4,5,6},
			{1,3,4,5,7},
			{2,3,4,5,8},
			{0,3,6,7,8},
			{1,4,6,7,8},
			{2,5,6,7,8}
	};
	
	long trans(int[] a){
		String s = "";
		for(int x:a)s+=x;
		return Long.parseLong(s);
	}
	
	int n;
	boolean sun[][];
	Set<Long>[][] set;
	
	//x日に雲がposに居てよいか
	boolean ok(int x, int pos){
		for(int i=0;i<4;i++)if(sun[x][cover[pos][i]])return false;
		return true;
	}
	
	boolean get(int x, int pos, int[] a){
		if(x==n)return true;
		if(set[x][pos].contains(trans(a)))return false;
		if(!ok(x, pos)){
			set[x][pos].add(trans(a));return false;
		}
		for(int j=0;j<5;j++){
			int[] t = new int[16];
			for(int i=0;i<16;i++)t[i]=a[i]-1;
			int nx = move[pos][j];
			for(int i=0;i<4;i++)t[cover[nx][i]] = 6;
			boolean f = true;
			for(int i=0;i<16;i++)if(t[i]<0)f = false;
			if(!f)continue;
			if(get(x+1, nx, t))return true;
		}
		set[x][pos].add(trans(a));
		return false;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			sun = new boolean[n][16];
			for(int i=0;i<n;i++)for(int j=0;j<16;j++)sun[i][j] = sc.nextInt()==1;
			set = new HashSet[n][9];
			for(int i=0;i<n;i++)for(int j=0;j<9;j++)set[i][j] = new HashSet<Long>();
			int[] a = new int[16];
			Arrays.fill(a, 5);
			if(!ok(0, 4)){
				System.out.println(0);continue;
			}
			for(int j=0;j<4;j++)a[cover[4][j]] = 6;
			System.out.println(get(0, 4, a)?1:0);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1243().run();
	}
}