POJ 2044 Weather Forecast

标题:2*2の雲と4*4の地域があります.雲に覆われたエリアは当日必ず雨が降り、雲には4種類の移動方法があります.しかし、都市部や祝日の間は雨が降らないようにし、7日間雨が降らない場所は1カ所ではできないことになっています.
考え方:まず一つの場所で7日連続で雨が降っていない場合を解決し、地図上のすべての場所を覆うには、4つの角を覆うだけでいい.そこに着くにはすべてを通過しなければならないからだ.そして状態の記録だ.vis[k][sign][a][b][c][d]は、k日目にsignの4つの格子の雨が降った場合を表す

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct node {
	int a,b,c,d;
	node():a(0), b(0), c(0), d(0) {}
};
struct point {
	int x,y;
	point(int _x, int _y):x(_x), y(_y) {}
};
const int dir[9][2] = {{0, 0}, {-1, 0}, {-2, 0}, {0, -1},
	{0, -2}, {1, 0}, {2, 0}, {0, 1}, {0, 2}};
int vis[370][9][7][7][7][7];
int day[370], n;

int getFlag(int i) {
	return 1<<i;
}

int check(int k, const point &u, const node &s) {	
	if (s.a == 7 || s.b == 7 || s.c == 7 || s.d == 7)
		return 0;
	int flag = 0;
	int x = u.x, y = u.y;
	flag |= getFlag(4*x+y) | getFlag(4*x+y+1);
	flag |= getFlag(4*(x+1)+y) | getFlag(4*(x+1)+y+1);
	if (flag & day[k])
		return 0;
	if (vis[k][4*x+y][s.a][s.b][s.c][s.d])
		return 0;
	vis[k][4*x+y][s.a][s.b][s.c][s.d] = 1;
	return 1;
}

int dfs(int k, const point &u, const node &state) {
	if (k == n)
		return 1;
	node s = state;
	s.a += 1, s.b += 1;
	s.c += 1, s.d += 1;
	if (u.x == 0 && u.y == 0)
		s.a = 0;
	else if (u.x == 0 && u.y == 2)
		s.b = 0;
	else if (u.x == 2 && u.y == 0)
		s.c = 0;
	else if (u.x == 2 && u.y == 2)
		s.d = 0;
	if (!check(k, u, s)) 
		return 0;
	for (int i = 0; i < 9; i++) {
		int nx = u.x + dir[i][0];
		int ny = u.y + dir[i][1];
		if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
			if (dfs(k+1, point(nx, ny), s))
				return 1;
	}
	return 0;
}

int main() {
	while (scanf("%d", &n) != EOF && n) {
		for (int i = 0; i < n; i++) {
			day[i] = 0;
			for (int j = 0; j < 16; j++) {
				int x;
				scanf("%d", &x);
				day[i] <<= 1;
				day[i] |= x;
			}
			memset(vis[i], 0, sizeof(vis[i]));
		}
		node s;
		if (dfs(0, point(1, 1), s))
			printf("1
");
		else printf("0
");
	}
	return 0;
}