1243-Weather Forecast

問題概要

4x4のマスがあり，日ごとに雨が降ってはいけないマスが与えられる．
2x2の雲を神様が動かすとき，雨が降ってはいけないマスには雨を降らさず，かつ，すべてのマスのうち7日間連続で雨が降らないことはないという条件を見たす，雲の動かしかたはあるか．

解法

メモ化DFS
雲の移動を全部試してみる．
"7日間連続で雨が降らないことはない"というのは4隅を調べるだけで十分．

実装(C++)

#include <cstdio>
#include <cstring>
using namespace std;
int n;
int data[365][4][4];
char ac[365][3][3][7][7][7][7];
int dx[4]={1,0,-1,0},q[4]={1,1,1,1};
int dfs(int d,int x,int y,int v[4]){
	int k[4]={v[0],v[1],v[2],v[3]};
	if(n==d)return 1;
	if(x==0&&y==0)k[0]=0;
	if(x==2&&y==0)k[1]=0;
	if(x==0&&y==2)k[2]=0;
	if(x==2&&y==2)k[3]=0;
	for(int i=0;i<4;i++){
		if(k[i]==7)return 0;
	}

	for(int xx=0;xx<4;xx++)for(int yy=0;yy<4;yy++){
		if(data[d][xx][yy]==1&&x<=xx&&xx<=x+1&&y<=yy&&yy<=y+1){
			return 0;
		}
	}
	if(ac[d][x][y][k[0]][k[1]][k[2]][k[3]])return 0;
	ac[d][x][y][k[0]][k[1]][k[2]][k[3]]=1;
	int next[4]={k[0]+1,k[1]+1,k[2]+1,k[3]+1};
	//雲を動かしてみる
	for(int j=0;j<3;j++){
		for(int i=0;i<4;i++){
			int nx=x+dx[i]*j,ny=y+dx[i^1]*j;
			if(nx>=0&&nx<3&&ny>=0&&ny<3){
				if(dfs(d+1,nx,ny,next))return 1;
			}
		}
	}
	return 0;
}
int main() {
	while(scanf("%d",&n),n){
		for(int i=0;i<n;i++){
			for(int x=0;x<4;x++){
				for(int y=0;y<4;y++){
					scanf("%d",&data[i][x][y]);
				}
			}
		}
		memset(ac,0,3*3*7*7*7*7*n);
		printf("%d\n",dfs(0,1,1,q));
	}
	return 0;
}