优化证明
#include <bits/stdc++.h>
using namespace std;
const int N = 366, M = 12, K = 2807;
const int dx[] = {0, -1, 1, 0, 0, -2, 2, 0, 0};
const int dy[] = {0, 0, 0, -1, 1, 0, 0, -2, 2};
int n;
int Q[N]; // 16 个村子每天的计划
bool vis[N][M][K]; //
struct Node // 四个角落的状态 (最近一次下雨)
{
int d[4];
}ID;
inline int get(int x, int y) // 坐标的二进制表示
{
return 1 << (x * 4 + y);
}
inline bool coor(int x, int y) // 判越界, 下标从 0 开始
{
return x >= 0 && x < 3 && y >= 0 && y < 3;
}
inline bool check(int now, int x, int y, Node cr)
{
for (int i = 0; i < 4; i ++ ) // 检查四个角落是否有超过 6 天未降雨
if (now - cr.d[i] > 6)
{
return false;
}
int weather = get(x, y) | get(x, y + 1) | get(x + 1, y) | get(x + 1, y + 1); // 云的二进制表示
if (weather & Q[now]) return false; // 与计划有交集
int s = 0, base = 8;
for (int i = 0; i < 4; i ++ )
s = s * base + (now - cr.d[i]); // 几天未下雨, 用四个七位二进制数存储状态
if (vis[now][x * 4 + y][s]) return false; // 记忆化搜索
return vis[now][x * 4 + y][s] = true; // 标记
}
inline bool DFS(int day, int x, int y, Node cr)
{
if (!check(day, x, y, cr)) return false;
if (day == n) return true; // 搜索结束
for (int i = 0; i < 9; i ++ ) // 9 种转移路径
{
Node ncr = cr;
int nx = x + dx[i], ny = y + dy[i];
if (!coor(nx, ny)) continue; // 越界
if (nx == 0 && ny == 0) ncr.d[0] = day + 1; // 左上角
if (nx == 0 && ny == 2) ncr.d[1] = day + 1; // 右上角
if (nx == 2 && ny == 0) ncr.d[2] = day + 1; // 左下角
if (nx == 2 && ny == 2) ncr.d[3] = day + 1; // 右下角
if (DFS(day + 1, nx, ny, ncr)) return true; // 下一天
}
return false;
}
void init()
{
memset(Q, 0, sizeof Q);
memset(vis, 0, sizeof vis);
ID = {0, 0, 0, 0};
vis[1][1 * 4 + 1][0] = 1; // 起始点
}
int main()
{
while (scanf("%d", &n) && n != 0)
{
init();
for (int i = 1; i <= n; i ++ )
for (int j = 0, q; j < 16; j ++ )
{
scanf("%d", &q);
Q[i] |= q << j;
}
printf("%d\n", DFS(1, 1, 1, ID));
}
return 0;
}