「Weather Forecast」 天气预报

GitHub跳转原题关系图返回列表

逐日推进的可达性 DP：状态只保留云的位置和「最近 6 天雨迹」的 6 个 16 位掩码，用集合合并等价状态，判罚退化成一次位运算。

OJ: roj

题目 ID: 3083

难度:提高

标签:搜索BFS状态压缩动态规划位运算python

创建: 2026-10-01 15:38

更新: 2026-10-07 13:50

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结
  4. 图示解析
    1. 云位置与覆盖掩码
    2. 雨迹数组的滑动

形式化题目

村子是 4×44 \times 4 的网格，区域按行优先编号 1∼161 \sim 16，其中中部四格 6,7,10,116,7,10,11 构成一个 2×22 \times 2 方块：

列 1 列 2 列 3 列 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

一片 2×22 \times 2 的云不能超出村子，因此它的左上角只能落在 3×3=93 \times 3 = 9 个位置上，把「云左上角在 (r,c)(r, c)」编码成 3r+c∈{0,…,8}3r + c \in \{0, \dots, 8\}；云在 (1,1)(1,1) 时覆盖的正是 6,7,10,116,7,10,11。

给定 NN 天的日程 a0,…,aN−1a_0, \dots, a_{N-1}，其中 ad⊆{1,…,16}a_d \subseteq \{1, \dots, 16\} 是第 d+1d+1 天「赶集过节、不能下雨」的区域集合。第 1 天云固定盖住 6,7,10,116,7,10,11 且不允许移动；此后每一天开始时可以把云向东、南、西、北平移 1 或 2 格，或原地不动（共 13 种位移）。记 coverd\text{cover}_d 为第 d+1d+1 天云覆盖的区域集合，一组方案合法当且仅当对每个 dd 都有

coverd∩ad=∅,∀i∈{1,…,16}, ∀d≥6:  i∈⋃t=d−6dcovert, \text{cover}_d \cap a_d = \varnothing, \qquad \forall i \in \{1,\dots,16\},\ \forall d \ge 6:\; i \in \bigcup_{t=d-6}^{d} \text{cover}_t ,

第二条说的是：只要日程里存在完整的 7 天窗口（d≥6d \ge 6），每块地在这个窗口内都必须至少下过一次雨，也就是不允许出现连续 7 天不下雨；d<6d < 6 时窗口还不满 7 天，条件自动满足。求是否存在合法方案。

样例 4 组数据的答案是 0 1 0 1：第 1 组第 1 天区域 6 就赶集，而云固定盖住 6,7,10,116,7,10,11，当天必然违规；第 3 组则在第 7 天走投无路。

正解

思路

先写出最朴素的搜索：dfs(第几天, 云位置, 每块地的连续干燥天数)，每天枚举 13 种位移，逐天检查上面两条约束。这个写法算法上是对的，但它会把同一个局面反复重算：不同的移动顺序可能走回同一个云位置、得到同一个干燥计数，后面那一整棵子树就白算了。搜索树分支约 13、深度 N≤365N \le 365，不去重就是 13N13^{N}，必须想办法合并等价局面。

要合并局面，先看「未来还受什么影响」。第 d+1d+1 天选择云位置时，只需要回答两件事：

  1. 这块云会不会淋到当天的赶集过节区？——这只取决于当天的云位置；
  2. 有没有哪块地已经旱满 6 天、今天必须轮到它？——这只取决于最近 6 天里下过雨的区域。

第 2 点是最关键的一步化简。直觉上要记录「每块地连续几天没下雨」，但那 16 个 0∼60 \sim 6 的计数器里， 真正影响判断的只有「最近 6 天内有没有下过雨」这一个布尔量：只要窗口内下过雨，计数就归零重来； 窗口内一天都没下，今天就必须下。于是把「16 个计数器」换成最近 6 天下过雨的区域并集 UU， 判罚变成

U‾∩cover‾=∅, \overline{U} \cap \overline{\text{cover}} = \varnothing ,

即「最近 6 天没被淋到的区域，今天必须全部被淋到」。因为窗口长度固定为 7， 逐天检查这个条件就等价于检查所有长度为 7 的窗口；而前 6 天窗口长度不足 7，判罚恒真，可以直接跳过。

接下来解决「怎么 O(1)O(1) 地滑动这个窗口」。若只存一个 UU，新的一天要先去掉 6 天前那一层，做不到。 所以改存前缀窗口的并集：WkW_k = 最近 k+1k+1 天下的雨的并集（k=0,1,…,5k = 0,1,\dots,5），于是

Wk′=coverd∪Wk−1 (k≥1),W0′=coverd, W'_k = \text{cover}_d \cup W_{k-1}\ (k \ge 1), \qquad W'_0 = \text{cover}_d ,

而判罚用的 UU 就是 W5W_5。注意 W0⊆W1⊆⋯⊆W5W_0 \subseteq W_1 \subseteq \dots \subseteq W_5 恒成立： WkW_k 就是「多往前看一天」的结果。新的一天只要「覆盖掩码与旧元组逐项取并」，O(1)O(1) 完成。

最后把 DFS 换成按天推进：既然只问「是否存在」，就不必记录路径，每层保存一个状态集合 (云位置, 雨迹)，集合天然合并等价状态。第 d+1d+1 天的集合由第 dd 天集合中每个状态枚举 13 种位移、筛掉违规者得到；集合空了就说明无解，可以立刻收工；走到最后一天仍非空就输出 1。

以样例第 2 组为例，一条合法轨迹的云位置编码是 4 → 3 → 0 → 2 → 8 → 6 → 7， 换成区域看就是 (6,7,10,11)→(5,6,9,10)→(1,2,5,6)→(3,4,7,8)→(11,12,15,16)→(9,10,13,14)→(10,11,14,15)(6,7,10,11) \to (5,6,9,10) \to (1,2,5,6) \to (3,4,7,8) \to (11,12,15,16) \to (9,10,13,14) \to (10,11,14,15)， 7 天里 16 块地每块都至少淋到一次。雨迹随天数滚动的过程如下（掩码按行优先，位 ii 对应区域 i+1i+1）：

天 云位置 当天覆盖 coverd\text{cover}_d 当日结束时的 W5W_5
1 4（1,1） 0000011001100000 0000011001100000
2 3（1,0） 0000001100110000 0000011101110000
3 0（0,0） 0000000000110011 0000011101110011
4 2（0,2） 0000000011001100 0000011111111111
5 8（2,2） 1100110000000000 1100111111111111
6 6（2,0） 0011001100000000 1111111111111111
7 7（2,1） 0110011000000000 1111111111111111

可以看到每块地都在 7 天窗口内被覆盖过，所以全程没有任何一次判罚被触发。

三个实现细节：

  • 第一天不是 13 选 1。题面规定第一天云盖住 6,7,10,116,7,10,11 且不允许移动，所以初态是唯一的 (CENTER, (COVER[CENTER],) * STREAK)；若第一天的日程在 6,7,10,116,7,10,11 上有 1（样例第 1 组）， 初态直接为空。雨迹要先填满 6 项（都填同一天），这样从第 2 天起 rain_hist[-1] 永远是 「最近 6 天雨迹」。
  • 判罚阈值。第 dd 天（0 起）只有在 d≥6d \ge 6 时窗口才满 7 天，代码用 enforce 参数控制； 写不写这个优化结果都一样，只是省一点常数。
  • 集合里存元组。雨迹用 tuple[int, ...] 当哈希键，省掉手工进制编码；状态相同时自动合并。

代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 15:38
# update_at: 2026-10-01 15:38

import sys

SIDE = 4                    # 村子是 4 x 4 的网格，区域按行优先编号 0..15
WINDOW = 2                  # 云是 2 x 2 的
SPOTS = SIDE - WINDOW + 1   # 云的左上角只能落在 3 x 3 个位置上
CENTER = SPOTS + 1          # 云在正中盖住中部 6-7-10-11，第一天它固定在这里
STREAK = 6                  # 同一块地连续 6 天不下雨还合法，第 7 天必须下
LAND_MASK = (1 << SIDE * SIDE) - 1

# 每天可选的位移：东南西北各 1 或 2 格，再加上原地不动，共 13 种。
MOVES = tuple(
    (dr, dc)
    for dr in range(-2, 3)
    for dc in range(-2, 3)
    if (dr == 0 or dc == 0) and abs(dr) + abs(dc) <= 2
)

# 以云位置 code = row * SPOTS + col 为下标的两张预处理表。
# COVER[code]：这块云淋到的 16 个区域，按行优先拍平成一个 16 位整数。
# NEXT[code]：这块云明天所有可选的左上角位置。
COVER = tuple(
    sum(
        1 << (r * SIDE + c)
        for r in range(row, row + WINDOW)
        for c in range(col, col + WINDOW)
    )
    for row in range(SPOTS)
    for col in range(SPOTS)
)  # 9 种云位置
NEXT = tuple(
    tuple(
        (row + dr) * SPOTS + col + dc
        for dr, dc in MOVES
        if 0 <= row + dr < SPOTS and 0 <= col + dc < SPOTS
    )
    for row in range(SPOTS)
    for col in range(SPOTS)
)  # 9 种云位置


def advance(
    states: set[tuple[int, tuple[int, ...]]], plan: int, enforce: bool
) -> set[tuple[int, tuple[int, ...]]]:
    """推进一步，返回下一天所有仍合法的 (云位置, 雨迹)。

    雨迹是 STREAK - 1 个 16 位掩码，第 k 项记录"最近 k+1 天里下过雨的区域并集"
    （最近一天就是当前云盖住的那片，随云的位置即可推出，不必另存）。
    plan 第 i 位为 1 表示区域 i 有赶集过节，当天不能下雨；enforce 为假表示
    历史还没攒满 6 天，这时不可能有人旱满 7 天，可以跳过判罚。
    """
    return {
        # 把今天的云并进每一项：旧的第 0 项是昨天的云，new_hist[-1] 就是"最近 6 天雨迹"
        (nxt, tuple(cover | rain for rain in (COVER[code],) + rain_hist[: STREAK - 2]))
        for code, rain_hist in states
        for nxt in NEXT[code]
        for cover in (COVER[nxt],)
        if not cover & plan                                     # 赶集过节的区域不能被淋到
        # 最近 6 天一滴雨没沾的区域今天必须轮到它下，否则就凑满 7 天旱
        and not (enforce and (LAND_MASK ^ rain_hist[-1]) & (LAND_MASK ^ cover))
    }


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        days = next(data)
        if days == 0:                                           # N = 0 表示输入结束
            break
        # 每一天的 16 个 0/1 压成一个掩码，第 i 位为 1 表示区域 i 有赶集过节。
        plans = [
            sum(next(data) << i for i in range(SIDE * SIDE))
            for _ in range(days)
        ]

        # 第一天云固定在正中间、不允许移动，于是它的位置是唯一确定的。
        states: set[tuple[int, tuple[int, ...]]] = set()
        if not plans[0] & COVER[CENTER]:                        # 中部有赶集过节就无解
            states.add((CENTER, (COVER[CENTER],) * (STREAK - 1)))

        for day, plan in enumerate(plans[1:], 1):
            states = advance(states, plan, day >= STREAK)
            if not states:                                      # 已经无解，剩下的日程不必再看
                break

        out.append("1" if states else "0")

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 17:44
 * update_at: 2026-10-06 17:44
 */

// 逐日推进的可达性 DP：
// 状态 = (云的左上角位置, 最近 6 天雨迹)。
// 雨迹不用 16 个"连续几天没下雨"计数器，而是存 6 个 16 位掩码 W[0..5]，
// W[k] 表示"最近 k+1 天下过雨的区域并集"，判罚只需读 W[5]：
// 最近 6 天没被淋到的区域，今天必须全部被淋到，等价于所有长度为 7 的窗口都合法。
// 每天枚举 13 种位移生成后继，用排序去重合并等价状态，集合空了就无解。

#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// 把 (云位置, W[0..5]) 打包成两个 64 位字作键：
// a 低 4 位是云位置，第 4..35 位放 W[0]、W[1]；b 依次放 W[2]、W[3]、W[4]、W[5]
// 六项都要存：W[5] 是最近 6 天的并集，不能由前 5 项推出
// （W[0]|...|W[4] 只是最近 5 天的并集，少一天）
typedef pair<ull, ull> Key;

Key pack_key(int code, int W0, int W1, int W2, int W3, int W4, int W5) {
    ull a = (ull)code | ((ull)W0 << 4) | ((ull)W1 << 20);
    ull b = (ull)W2 | ((ull)W3 << 16) | ((ull)W4 << 32) | ((ull)W5 << 48);
    return Key(a, b);
}


const int SIDE = 4;               // 村子是 4 x 4 的网格
const int SPOTS = 3;              // 云是 2 x 2，左上角只能落在 3 x 3 个位置
const int CENTER = 4;             // 云在正中 (1,1) 时盖住 6,7,10,11，第一天固定在这里
const int STREAK = 6;             // 同一块地连续 6 天不下雨还合法，第 7 天必须下
const int NDAY = 370;             // N <= 365，数组多开一点

int n;                            // 本组用例的天数
int plan[NDAY];                   // plan[d]：第 d 天赶集过节区域的 16 位掩码（1 表示不能淋雨）

int cover_mask[SPOTS * SPOTS];    // cover_mask[code]：云在 code 位置淋到的区域掩码，code = 行*3+列
vector<int> nxt[SPOTS * SPOTS];   // nxt[code]：从 code 出发一天内能到的所有云位置（含原地不动）
bool vis[SPOTS * SPOTS];          // 预处理 nxt 时的临时标记

// 当前层和下一层的状态集合。逐层滚动，不保存历史层。
vector<Key> cur_list, next_list;

// 云左上角在 (r,c)（行列从 0 开始）时覆盖的区域掩码，16 位按行优先
int mask_at(int r, int c) {
    return (1 << (r * SIDE + c)) | (1 << (r * SIDE + c + 1))
         | (1 << ((r + 1) * SIDE + c)) | (1 << ((r + 1) * SIDE + c + 1));
}

// 预处理 9 个覆盖掩码和每个位置一天内的 13 种位移
void prepare() {
    for (int r = 0; r < SPOTS; r++)
        for (int c = 0; c < SPOTS; c++)
            cover_mask[r * SPOTS + c] = mask_at(r, c);
    // 位移：东南西北各 1 或 2 格，或原地不动，不允许对角线
    for (int code = 0; code < SPOTS * SPOTS; code++) {
        memset(vis, 0, sizeof(vis));
        int r = code / SPOTS, c = code % SPOTS;
        for (int dr = -2; dr <= 2; dr++)
            for (int dc = -2; dc <= 2; dc++) {
                if (dr != 0 && dc != 0) continue;      // 不允许对角线
                if (dr * dr + dc * dc > 4) continue;   // 距离超过 2 格
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= SPOTS || nc < 0 || nc >= SPOTS) continue;
                int ncode = nr * SPOTS + nc;
                if (!vis[ncode]) {
                    vis[ncode] = true;
                    nxt[code].push_back(ncode);
                }
            }
    }
}

// 检查今天 (第 d 天，0 起) 的转移是否合法；enforce 为真时 7 天窗口已满
bool check_day(int cover, ull U, bool enforce, int planmask) {
    // 约束 1：当天不能淋到赶集过节区
    if (cover & planmask) return false;
    // 约束 2：最近 6 天没淋到的区域（~U），今天必须全部淋到
    if (enforce) {
        int dry = (~U) & 0xFFFF;          // 旱满 6 天的区域
        if (dry & (~cover & 0xFFFF)) return false; // 今天淋不到就违规
    }
    return true;
}

void solve() {
    for (int d = 0; d < n; d++) {
        int m = 0;
        for (int i = 0; i < SIDE * SIDE; i++) {
            int x;
            scanf("%d", &x);
            if (x) m |= 1 << i;
        }
        plan[d] = m;
    }

    // 第一天云固定盖住 6,7,10,11 且不允许移动，所以初态唯一；
    // 雨迹 6 项都填第一天的覆盖，从第 2 天起 U 永远是"最近 6 天雨迹"
    int c0 = cover_mask[CENTER];
    cur_list.clear();
    // 第一天也不允许淋到赶集过节区，违规则直接无解
    if (!(c0 & plan[0]))
        cur_list.push_back(pack_key(CENTER, c0, c0, c0, c0, c0, c0));

    for (int d = 1; d < n; d++) {
        bool enforce = (d >= STREAK);   // 第 7 天（d=6）起窗口才满 7 天
        next_list.clear();
        // 由当天集合里的每个状态，枚举 13 种位移生成后继
        for (int i = 0; i < (int)cur_list.size(); i++) {
            Key key = cur_list[i];
            int code = (int)(key.first & 15);
            // 从键里拆出 W[0..5]，U = 六项的并 = 最近 6 天雨迹
            int W[6];
            W[0] = (int)((key.first >> 4) & 0xFFFF);
            W[1] = (int)((key.first >> 20) & 0xFFFF);
            W[2] = (int)(key.second & 0xFFFF);
            W[3] = (int)((key.second >> 16) & 0xFFFF);
            W[4] = (int)((key.second >> 32) & 0xFFFF);
            W[5] = (int)((key.second >> 48) & 0xFFFF);
            int U = W[0] | W[1] | W[2] | W[3] | W[4] | W[5];
            for (int j = 0; j < (int)nxt[code].size(); j++) {
                int ncode = nxt[code][j];
                int cover = cover_mask[ncode];
                if (!check_day(cover, U, enforce, plan[d])) continue;
                // W'[k] = cover | W[k-1]，W'[0] = cover
                next_list.push_back(pack_key(ncode, cover, cover | W[0],
                                             cover | W[1], cover | W[2],
                                             cover | W[3], cover | W[4]));
            }
        }
        // 排序去重，合并等价状态
        sort(next_list.begin(), next_list.end());
        next_list.erase(unique(next_list.begin(), next_list.end()), next_list.end());
        cur_list.swap(next_list);
        if (cur_list.empty()) break;   // 集合空了，后面再也不可能有合法方案
    }

    printf("%d\n", cur_list.empty() ? 0 : 1);
}

int main() {
    prepare();
    while (scanf("%d", &n) == 1 && n != 0) solve();
    return 0;
}

复杂度

设单层状态数上界为 SS。每天对每个状态枚举至多 13 种位移，每次转移是常数次 16 位位运算和一次 长度为 6 的元组构造，均为 O(1)O(1)，所以单组用例是 O(N⋅S)O(N \cdot S)，空间 O(S)O(S)（逐日滚动， 不保存历史层）。

SS 的实测上界是 2416（365 天全晴天，此时云可以到处跑、状态最丰富），N≤365N \le 365。 单组最坏情况下各层状态数之和约 8.6×1058.6 \times 10^{5}，每条状态枚举至多 13 个后继、 共约 1.1×1071.1 \times 10^{7} 次转移检查，本地约 0.8s；真实数据 27 组（含两组 N=365N = 365）合计 0.32s。 雨迹虽然形式上是一个 16 位掩码，但它只由 9 种覆盖掩码的并集生成，可达取值远少于 2162^{16}， 所以状态集合并不会膨胀。

对比：朴素搜索是 O(13N)O(13^{N})；如果按「云位置 + 16 个精确干燥计数」去重，状态上限是 9×7169 \times 7^{16}，仍然不可行——把计数换成并集正是本题的关键。

总结

本题的骨架是逐层可达性 DP / 搜索：

  • 状态 = 云位置（9 种）+ 最近 6 天的雨迹；
  • 雨迹用「前缀窗口并集」的 6 个 16 位掩码表示，逐日 O(1)O(1) 滚动；
  • 两类约束都退化成位运算：cover & plan 查赶集过节，~U & ~cover 查是否旱满 7 天；
  • 每层用集合合并等价状态，集合空了立即输出 0。

真正的难点不在搜索，而在状态设计：把「每块地连续几天没下雨」压缩成「最近 6 天有没有下过雨」， 状态空间才从 7167^{16} 降到几千。这类「只关心窗口内是否发生过」的约束，都可以尝试用并集/前缀 掩码代替计数器。

图示解析

云位置与覆盖掩码

下表把云的 9 种合法左上角位置与其编码列出来，行列下标从 0 开始。

行 \ 列 0 1 2
0 0 1 2
1 3 4（第一天） 5
2 6 7 8

云位置可以直接平移到「区域编号的位掩码」：位置 4 对应 0000011001100000，位置 0 对应 0000000000110011。预先算好这 9 个掩码和每种的后续位置表，逐日推进时就只剩位运算。 第一天固定在 4，所以前 6 天的雨迹一定包含 0000011001100000。

雨迹数组的滑动

用全晴天日程、并让云按 4 → 1 → 0 → 0 移动，观察状态里的雨迹数组如何逐项变化 （这里只列前 3 项，W0W_0 是最新的一天）：

天 云位置 W0W_0 W1W_1 W2W_2 …
2 1 0000000001100110 0000011001100110 0000011001100110 …
3 0 0000000000110011 0000000001110111 0000011001110111 …
4 0 0000000000110011 0000000000110011 0000000001110111 …

每一行都是把新一天的覆盖掩码分别并到上一状态的第 0..40..4 项上（对应代码里的 rain_hist[:5]）， 第一项单独立为当天的覆盖掩码。上一状态的第 6 项（最早、覆盖天数最多的那一项）被直接丢弃—— 这就是窗口「滑出」一天的机制：每一项每前进一天就代表多往前看一天，攒到 6 天就被挤下去。 所以 WkW_k 恒定表示「最近 k+1k+1 天下过雨的区域」，判罚只需读最后一项 W5W_5。