问题背景

题目要求我们通过移动一朵 2×2 的云，来控制一个 4×4 区域的天气，目标是满足以下条件：

1. 市场和节日区域不能下雨：给定的时间表中，标记为 1 的区域表示当天是市场或节日，不能下雨。
2. 每个区域不能连续 7 天没有雨水：最多允许连续 6 天没有雨。
3. 初始状态：第一天中央区域（6、7、10、11）正在下雨。
4. 移动规则：云可以向四个方向（北、南、东、西）移动 1 格或 2 格，也可以保持不动，但不能对角移动。

我们需要判断是否能在给定的时间段内满足所有条件。

难点分析

1. 状态管理：需要记录每个区域的连续无雨天数，以及云的位置。
2. 搜索空间：云的位置和移动方式较多，直接暴力搜索可能会超时。
3. 剪枝优化：需要通过记忆化搜索等方式减少重复计算。

解题思路

1. 状态表示：

   • 使用一个整数 state 表示当天所有区域是否为市场或节日（1 表示节日，0 表示普通天）。
   • 使用一个结构体 Node 记录四个角落（左上、右上、左下、右下）最后一次下雨的天数。
   • 使用 vis 数组记录已经搜索过的状态，避免重复计算。

2. 深度优先搜索（DFS）：

   • 从第一天开始，云位于中央区域（1,1）。
   • 每天尝试将云移动到所有可能的位置（包括保持不动）。
   • 检查当前状态是否合法：
     • 云覆盖的区域不能是市场或节日。
     • 任何区域的连续无雨天数不能超过 6 天。
   • 如果到达最后一天且状态合法，返回 true；否则继续递归搜索。

3. 剪枝：

   • 使用记忆化搜索，记录已经计算过的状态，避免重复计算。

代码实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 366; // 最多 365 天
const int M = 10;  // 云的位置状态
const int MAXN = 2807; // 状态压缩后的最大值
const int dx[] = {0, -1, 1, 0, 0, -2, 2, 0, 0}; // 云的移动方向
const int dy[] = {0, 0, 0, -1, 1, 0, 0, -2, 2};

int n; // 时间段天数
int state[N]; // 每天的市场和节日状态
bool vis[N][M][MAXN]; // 记忆化搜索数组

// 用于记录四个角落最后一次下雨的天数
struct Node {
    int d[4];
} st;

// 获取某个区域的状态（是否下雨）
inline int Get(int x, int y) {
    return 1 << (x * 4 + y);
}

// 检查当前状态是否合法
inline bool check(int now, int x, int y, Node cr) {
    for (int i = 0; i < 4; ++i) {
        if (now - cr.d[i] > 6) return false; // 检查是否有区域连续 7 天无雨
    }
    int weather = Get(x, y) | Get(x, y + 1) | Get(x + 1, y) | Get(x + 1, y + 1);
    if (weather & state[now]) return false; // 检查云覆盖区域是否为市场或节日
    int s = 0, base = 8;
    for (int i = 0; i < 4; ++i) {
        s = s * base + (now - cr.d[i]); // 状态压缩
    }
    if (vis[now][x * 4 + y][s]) return false; // 记忆化剪枝
    return vis[now][x * 4 + y][s] = true;
}

// 检查云的位置是否合法
inline bool valid(int x, int y) {
    return (x >= 0 && x < 3 && y >= 0 && y < 3); // 云不能越界
}

// 深度优先搜索
bool Dfs(int dep, int x, int y, Node cr) {
    if (!check(dep, x, y, cr)) return false; // 当前状态不合法
    if (dep == n) return true; // 到达最后一天且状态合法
    for (int i = 0; i < 9; ++i) { // 尝试所有可能的移动
        int nx = x + dx[i], ny = y + dy[i];
        Node ncr = cr;
        if (!valid(nx, ny)) continue; // 云越界
        if (nx == 0 && ny == 0) ncr.d[0] = dep + 1;
        if (nx == 0 && ny == 2) ncr.d[1] = dep + 1;
        if (nx == 2 && ny == 0) ncr.d[2] = dep + 1;
        if (nx == 2 && ny == 2) ncr.d[3] = dep + 1;
        if (Dfs(dep + 1, nx, ny, ncr)) return true; // 递归搜索
    }
    return false;
}

// 处理每个数据集
void work() {
    memset(state, 0, sizeof(state));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 16; ++j) {
            int val;
            cin >> val; // 读取当天的市场和节日状态
            state[i] |= (val << j);
        }
    }
    st.d[0] = st.d[1] = st.d[2] = st.d[3] = 0; // 初始化四个角落的下雨天数
    vis[1][1 * 4 + 1][0] = 1; // 初始状态标记
    cout << (Dfs(1, 1, 1, st) ? 1 : 0) << endl; // 输出结果
}

int main() {
    while (true) {
        cin >> n;
        if (!n) break; // 输入 0 结束
        work();
    }
    return 0;
}

代码注释说明

1. Get 函数：

   • 通过位运算获取某个区域的状态（是否下雨）。
   • 1 << (x * 4 + y) 将第 (x, y) 个区域的状态存储在整数的对应位上。

2. check 函数：

   • 检查当前状态是否合法：
     • 检查是否有区域连续 7 天没有雨水。
     • 检查云覆盖的区域是否为市场或节日。
     • 使用状态压缩和记忆化搜索避免重复计算。

3. valid 函数：

   • 检查云的位置是否越界。

4. Dfs 函数：

   • 使用深度优先搜索尝试所有可能的云移动方式。
   • 如果当前状态合法且到达最后一天，返回 true。
   • 否则递归搜索下一天的状态。

5. work 函数：

   • 初始化状态数组和记忆化数组。
   • 读取输入数据并存储到 state 中。
   • 调用 Dfs 函数从第一天开始搜索。

6. 主函数：

   • 循环读取每个数据集，直到输入为 0 时结束。

总结

通过深度优先搜索和记忆化剪枝，我们能够在合理的时间内解决这个问题。代码中使用了状态压缩和记忆化搜索来优化性能，避免了不必要的重复计算。