题目描述
你是一个可以控制风的神仙。
通过把云吹到不同的位置,你可以控制降雨。
云下地区会降雨,没有云的地方阳光灿烂。
你是一个仁慈的神,希望土地在平时可以有足够的雨水,在赶集和过节能够充满阳光。
你负责掌控一个村子的天气状况。
这个村子呈 4×4 的网格状分布,村子内的每个区域被编号如下图所示:
你拥有一片 2×2 大小的云,这片云不能到村子以外的地方。
你将获得一段时间内村子每个区域的赶集和过节时间表。
在这段时间的第一天,中部地区(6−7−10−11)将会下雨。
在接下来的每一天中,您可以在四个基本方向(东南西北)之中选取一个方向,将云移动 1 或 2 个方格,或将其保持在相同位置。
不允许对角线移动,所有动作都在一天开始时发生。
任何地区都不能连续七天或以上时间都不降雨。
这段时间以外的日子的下雨状况你无需做任何考虑。
算法1
bfs
/*
整体思路:用bfs做,记忆化搜索,跟DP有那么一点关系
我们稍微推一下就可以得出,只要四个角不连续7天不下雨,那么中间也不会
(https://cdn.luogu.com.cn/upload/image_hosting/roo4sid4.png)
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 366;
struct sb
{
int day, x, y, s0, s1, s2, s3;
};
int n;
int st[N][3][3][7][7][7][7];
int state[N][4][4];
int bfs()
{
int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};//四方偏移量 + 不动
if (state[1][1][1] || state[1][1][2] || state[1][2][1] || state[1][2][2]) return 0;//开头特判
queue<sb> q;
memset(st, 0, sizeof st);
q.push({1, 1, 1, 1, 1, 1, 1});
st[1][1][1][1][1][1][1] = true;//第一天
while (q.size())
{
auto t = q.front();//取出队头
q.pop();
if (t.day == n) return 1;//可行
int x = t.x, y = t.y;
for (int i = 0; i < 5; i ++ )
for (int j = 1; j <= 2; j ++ )
{
int a = x + dx[i] * j, b = y + dy[i] * j;//四方偏移 + 不动
if (a < 0 || a > 2 || b < 0 || b > 2) continue;
auto s = state[t.day + 1];
if (s[a][b] || s[a][b + 1] || s[a + 1][b] || s[a + 1][b + 1]) continue;
int s0 = t.s0, s1 = t.s1, s2 = t.s2, s3 = t.s3;
if (!b && !a) s0 = 0;
else if ( ++ s0 == 7) continue;
if (!a && b == 2) s1 = 0;
else if ( ++ s1 == 7) continue;//更新 + 判断是否可行
if (a == 2 && !b) s2 = 0;
else if ( ++ s2 == 7) continue;
if (b == 2 && a == 2) s3 = 0;
else if ( ++ s3 == 7) continue;
if (st[t.day + 1][a][b][s0][s1][s2][s3]) continue;
st[t.day + 1][a][b][s0][s1][s2][s3] = true;
q.push({t.day + 1, a, b, s0, s1, s2, s3});//下一层
}
}
return 0;
}
int main()
{
while (cin >> n, n)
{
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < 4; j ++ )
for (int k = 0; k < 4; k ++ )//读入
cin >> state[i][j][k];
cout << bfs() << endl;//bfs求解
}
return 0;
}
结构体名称瞩目(