题解：P10492 Weather Forecast

· · 题解

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;
}