性质:四个角下雨天是相邻三个格子下雨天的子集.
简证:以左上角为例,当1下雨时,2,5,6必然下雨,而2,5,6下雨时,1可能不下雨.
因此,每个格子7天内都下过雨当且仅当四个角七天内下过雨.
有一说一,BaseAI那步状压没啥意义
记$f(now,loc,d1,d2,d3,d4)$表示在第$i$天,左上角在$loc$,第$i$个角(左上,右上,左下,右下标号)已经$di$天没下雨了
枚举9种方式转移即可,用记搜实现.(为啥要放在搜索这章呢,因为记搜也算搜索?)
时间复杂度$\mathcal O(SnT),S$是格子数,$n$是天数,$T$是转移数.
/**********/
#define MAXN 411
bool vis[MAXN][17][7][7][7][7],f[MAXN][17][7][7][7][7];
bool a[MAXN][17];
ll n;
const ll mx[]={0,0,1,0,-1,0,2,0,-2},my[]={0,1,0,-1,0,2,0,-2,0};
bool dfs(ll now,ll s,ll d1,ll d2,ll d3,ll d4)
{
ll x=(s-1)/4+1,y=(s-1)%4+1;
if(x==1&&y==1)d1=0;
else if(x==1&&y==3)d2=0;
else if(x==3&&y==1)d3=0;
else if(x==3&&y==3)d4=0;
bool &cur=f[now][s][d1][d2][d3][d4];
if(vis[now][s][d1][d2][d3][d4])return cur;
if(d1>6||d2>6||d3>6||d4>6)return cur=0;
if(a[now][s]|a[now][s+1]|a[now][s+4]|a[now][s+5])return cur=0;
vis[now][s][d1][d2][d3][d4]=1;
if(now==n)return 1;
for(ll i=0;i<9;++i)
{
ll vx=(s-1)/4+1+mx[i],vy=(s-1)%4+1+my[i];
if(vx>0&&vx<=3&&vy>0&&vy<=3)
if(dfs(now+1,(vx-1)*4+vy,d1+1,d2+1,d3+1,d4+1))return cur=1;
}
return cur=0;
}
int main()
{
while(n=read())
{
for(ll i=1;i<=n;++i)
for(ll j=1;j<=16;++j)a[i][j]=read();
memset(vis,0,sizeof vis);memset(f,0,sizeof f);
if(dfs(1,6,1,1,1,1))puts("1");
else puts("0");
}
}