#84. 「Weather Forecast」 天气预报

「Weather Forecast」 天气预报

你是一个可以控制风的神仙。

通过把云吹到不同的位置,你可以控制降雨。

云下地区会降雨,没有云的地方阳光灿烂。

你是一个仁慈的神,希望土地在平时可以有足够的雨水,在赶集和过节能够充满阳光。

你负责掌控一个村子的天气状况。

这个村子呈4 x 4的网格状分布,村子内的每个区域被编号如下图所示:

天气.jpg

你拥有一片2 x 2大小的云,这片云不能到村子以外的地方。

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

在这段时间的第一天,中部地区(6-7-10-11)将会下雨。

在接下来的每一天中,您可以在四个基本方向(东南西北)之中选取一个方向,将云移动1或2个方格,或将其保持在相同位置。

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

任何地区都不能连续七天或以上时间都不降雨。

这段时间以外的日子的下雨状况你无需做任何考虑。

输入格式

输入包含多组测试用例。

对于每组测试用例,第一行包含一个整数N,表示这段时间的具体天数。

接下里N行,描绘了接下来N天的赶集和过节时间表,第i行表示第i天的时间表。

这N行里,每行包含16个数字(0或1),0表示正常的一天,1表示赶集和过节的一天,第i个数字表示第i个区域的具体情况。

每行数字之间用空格隔开。

当输入测试用例N=0时,表示输入终止,且该用例无需处理。

输出格式

每个测试用例输出一个整数0或1,如果可以保证整个时间段内,该下雨的地方下雨,不该下的地方不下,则输出1。

如果不能保证则输出0,每个结果占一行。

数据范围

1N3651 \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

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解