云神降雨问题

题目描述

你是一个可以控制风的神仙。通过把云吹到不同的位置，你可以控制降雨。

村庄布局

村子呈 4×4 的网格状分布，村子内的每个区域编号如下：

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

云的特性

• 你拥有一片 2×2 大小的云，这片云不能到村子以外的地方
• 云覆盖的4个区域会下雨，没有云覆盖的地方阳光灿烂

时间安排

你将获得一段时间内村子每个区域的赶集和过节时间表。

初始状态：

• 在这段时间的第一天，中部地区（6-7-10-11）将会下雨
• 即初始时云覆盖区域6,7,10,11

移动规则： 在接下来的每一天中，您可以在**四个基本方向（东、南、西、北）**之中选取一个方向，将云移动 1 或 2 个方格，或将其保持在相同位置

• 不允许对角线移动
• 所有动作都在一天开始时发生

约束条件

1. 时间表要求：根据每天的时间表，赶集和过节的地方（标记为1）必须阳光灿烂（不能下雨），正常日子（标记为0）没有特殊要求
2. 连续干旱限制：任何地区都不能连续七天或以上时间都不降雨
3. 边界限制：云不能移动到村子以外的地方
4. 时间范围：只考虑这N天内的天气状况，这段时间以外的日子无需考虑

输入格式

输入包含多组测试用例。

对于每组测试用例：

• 第一行包含一个整数 N，表示这段时间的具体天数
• 接下来 N 行，描绘了接下来 N 天的赶集和过节时间表，第 i 行表示第 i 天的时间表
• 每行包含 16 个数字（0或1）：
  • 0 表示正常的一天
  • 1 表示赶集和过节的一天
  • 第 i 个数字表示第 i 个区域的具体情况
• 每行数字之间用空格隔开
• 当输入测试用例 N=0 时，表示输入终止，且该用例无需处理

输出格式

每个测试用例输出一个整数 0 或 1：

• 如果可以保证整个时间段内，该下雨的地方下雨，不该下的地方不下，则输出 1
• 如果不能保证则输出 0

每个结果占一行。

数据范围

$1 \le N \le 365$

输入样例

1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0

输出样例

0
1
0
1

样例解释

第一个测试用例：N=1

• 只有1天
• 时间表：区域6标记为1（赶集过节），其他区域为0
• 初始状态：云覆盖区域6,7,10,11，即区域6下雨
• 但区域6是赶集过节日，必须阳光灿烂
• 无法满足条件，输出 0

第二个测试用例：N=7

• 有7天
• 存在一种移动方案满足所有条件：
  1. 赶集过节的地方（标记1）没有云覆盖
  2. 没有区域连续7天不下雨
• 输出 1

第三个测试用例：N=7

• 无法找到满足所有条件的移动方案
• 输出 0

第四个测试用例：N=15

• 存在满足条件的移动方案
• 输出 1

关键点

1. 云的位置：2×2的云有9种可能位置（在4×4网格内）
2. 移动方式：每天可以向东、南、西、北移动1或2格，或不动
3. 约束冲突：
   • 时间表要求：标记1的区域不能下雨
   • 干旱限制：任何区域不能连续7天不下雨
4. 状态表示：需要记录云的位置和每个区域连续不下雨的天数

时空限制

• 时间限制：1秒
• 空间限制：64MB