自动搬运

查看原文

来自洛谷，原作者为

	Ashford 在线|剩余复活币:1 初二|卷题，卷题，还tmd是卷题

搬运于2025-08-24 22:58:31，当前版本为作者最后更新于2025-07-19 09:11:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10492 Weather Forecast

这个问题可以通过记忆化搜索结合状态压缩来解决。核心思路是只跟踪四个角落的干燥天数，并利用 DFS 遍历所有可能的云移动路径。通过剪枝（检查云是否覆盖活动区域、角落干燥天数是否超限）优化。状态转移时枚举所有合法移动方向并更新角落的干燥天数，最终判断是否存在合法路径满足所有约束条件。时间复杂度为 $O (N)$，空间复杂度为 $O (N×3×3×7⁴)$，其中 $N$ 为天数。

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 370;
int n,a[MAXN][5][5],f[5][5][MAXN][8][8][8][8];
bool check(int day, int x, int y) {
	for(int i=x; i<=x+1; i++) {
		for(int j=y; j<=y+1; j++) {
			if(a[day][i][j] == 1) return false;
		}
	}
	return true;
}
int dfs(int x, int y, int day, int zs, int zx, int ys, int yx) {
	if(f[x][y][day][zs][zx][ys][yx] != -1) return f[x][y][day][zs][zx][ys][yx];
	if(!check(day, x, y)) return 0;
	if(zs >= 7 || zx >= 7 || ys >= 7 || yx >= 7) return 0;
	if(day == n) return 1;
	int dx[] = {-1, 0, -2, 0, 2, 0, 1, 0, 0},dy[] = {0, -1, 0, -2, 0, 2, 0, 1, 0},ans = 0;
	for(int i = 0; i < 9; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if(1 <= nx && nx <= 3 && 1 <= ny && ny <= 3) {
			int new_zs = (nx == 1 && ny == 1) ? 0 : zs + 1;
			int new_zx = (nx == 3 && ny == 1) ? 0 : zx + 1;
			int new_ys = (nx == 1 && ny == 3) ? 0 : ys + 1;
			int new_yx = (nx == 3 && ny == 3) ? 0 : yx + 1;
			ans |= dfs(nx, ny, day + 1, new_zs, new_zx, new_ys, new_yx);
		}
	}
	f[x][y][day][zs][zx][ys][yx] = ans;
	return ans;
}
int main() {
	while(1) {
		memset(f, -1, sizeof(f));
		cin>>n;
		if(n == 0) break;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= 4; j++) {
				for(int k = 1; k <= 4; k++) {
					cin>>a[i][j][k];
				}
			}
		}
		cout << dfs(2, 2, 1, 1, 1, 1, 1) << "\n";
	}
	return 0;
}