记录编号	604955	评测结果	A
题目名称	2515.[POJ 2044]天气预报	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	0.319 s
提交时间	2025-08-12 18:08:52	内存使用	103.88 MiB

#include<bits/stdc++.h>
using namespace std;
int a[400][5][5];
int dp[400][4][4][8][8][8][8];
int dir[9][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {2, 0}, {-2, 0}, {0, 2}, {0, -2}, {0, 0}};
bool check(int step, int x, int y)
{
	for (int i = x; i <= x + 1; i++) {
		for(int j = y; j <= y + 1; j++) {
			if(a[step][i][j] == 1) {
				return false;
			} 
		}
	}
	return true;
}
int n;
bool dfs(int step, int x, int y, int x1, int x2, int y1, int y2)
{
	if (dp[step][x][y][x1][x2][y1][y2] >= 0) {
		return dp[step][x][y][x1][x2][y1][y2];
	}
	if (!check(step, x, y)) {
		return 0;
	}
	if (x1 >= 7 || x2 >= 7 || y1 >= 7 || y2 >= 7) {
		return 0;
	}
	if (step == n) {
		return 1;
	}
	int res = 0;
	for (int i = 0; i < 9; i++) {
		int xx = x + dir[i][0];
		int yy = y + dir[i][1];
		if (1 > xx || xx > 3 || 1 > yy || yy > 3) {
			continue;
		}
		res |= dfs(step + 1, xx, yy, (xx == 1 && yy == 1) ? 0 : x1 + 1, (xx == 3 && yy == 1) ? 0 : x2 + 1, (xx == 1 && yy == 3) ? 0 : y1 + 1, (xx == 3 && yy == 3) ? 0 : y2 + 1);
	}

	dp[step][x][y][x1][x2][y1][y2] = res;
	return res;
}
signed main()
{
	while (1) {
		cin >> n;
		if (!n) {
			return 0;
		}
		memset(dp, -1, sizeof (dp));
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 4; j++) {
				for (int k = 1; k <= 4; k++) {
					cin >> a[i][j][k];
				}
			}
		}
		cout << dfs(1, 2, 2, 1, 1, 1, 1) << '\n';
	}
	return 0;
}