题目描述
你是一个可以控制风的神仙。通过把云吹到不同的位置,你可以控制降雨。云下地区会降雨,没有云的地方阳光灿烂。你是一个仁慈的神,希望土地在平时可以有足够的雨水,在赶集和过节能够充满阳光。你负责掌控一个村子的天气状况。这个村子呈 4×4 的网格状分布。你拥有一片2x2大小的云,这片云不能到村子以外的地方。你将获得一段时间内村子每个区域的赶集和过节时间表。在这段时间的第一天,中部地区(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,每个结果占一行。
数据范围
1≤N≤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
算法1
状态、暴力搜索
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=366;
bool f[N][3][3][7][7][7][7]; //N:days, 3:x/y,7:no rain days
bool vis[N][3][3][7][7][7][7];
bool holi[N][4][4];
int n;
struct Node{
int day,x,y,a,b,c,d;
};
bool check(int i,int x,int y){
return holi[i][x][y] | holi[i][x+1][y] | holi[i][x][y+1] | holi[i][x+1][y+1];
}
int bfs(){
if(check(1,1,1)) return 0;
queue<Node> q;
memset(vis,0,sizeof vis);
q.push({1,1,1,1,1,1,1});
vis[1][1][1][1][1][1][1]=true;
int dt[]={0, 1, 0, -1, 0, 0}; //{dt[i], dt[i+1]}: dir
while(q.size()){
auto t=q.front();
q.pop();
if(t.day==n)return 1;
for(int i=0,j=0;i<5;j^=1,i+=(j^1)){
int x=t.x+dt[i]*(j+1),y=t.y+dt[i+1]*(j+1);
if(x<0 || x>2 || y<0 || y>2) continue;
if(check(t.day+1,x,y))continue; //holiday
int day=t.day+1, a=t.a, b=t.b, c=t.c, d=t.d;
a=(x==0 && y==0 ? 0 : a+1);
b=(x==0 && y==2 ? 0 : b+1);
c=(x==2 && y==0 ? 0 : c+1);
d=(x==2 && y==2 ? 0 : d+1);
if(a==7 || b==7 || c==7 || d==7) continue;
if(vis[day][x][y][a][b][c][d])continue;
vis[day][x][y][a][b][c][d]=true;
q.push({day,x,y,a,b,c,d});
}
}
return 0;
}
int main(){
while(cin>>n,n){
for(int i=1;i<=n;i++)
for(int j=0;j<16;j++)
cin>>holi[i][j/4][j%4];
cout<<bfs()<<endl;
}
return 0;
}