usaco-5.2.3 威斯康星州的牧场

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

位掩码 DFS + 记忆化：换入字母必不等于原字母，剩余需求由棋盘唯一推出，8 邻域检查用位运算完成，字典序扩展直接得到最小方案并统计全部合法序列数。

OJ: roj

题目 ID: 2081

难度:普及

标签:搜索剪枝记忆化搜索位运算

创建: 2026-10-01 07:52

更新: 2026-10-06 10:45

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

4×44 \times 4 的牧场上每格住着一群奶牛（字母 A∼EA \sim E），要依次执行 16 次搬运：每次选一个字母 tt 和一个格子 (r,c)(r,c) 把该格换成 tt，每个格子恰好被换一次；放 tt 时该格当前不能是 tt，且它的 8 邻域（含对角线）中当前也不能有 tt，第一步必须放 DD，各字母要放入的群数固定为 A,B,C×3, D×4, E×3A,B,C \times 3,\ D \times 4,\ E \times 3。

输入四行，每行一个 4 字母字符串表示初始棋盘（如样例 ABAC / DCDE / BEBC / CADE）；输出字典序最小（先比字母、再比行、再比列）的 16 步方案，每行 字母 行 列（行列从 1 开始），即 D 4 1、C 4 2、A 3 1、A 3 3、B 2 4、B 3 2、B 4 4、E 2 1、E 2 3、D 1 4、D 2 2、C 1 1、C 1 3、A 1 2、E 4 3、D 3 4，最后多输出一行合法方案总数（样例为 14925）。

思路

回溯搜索每步枚举"放哪个字母、放哪个格子"，用位掩码做安全检查：occ[t] 记录当前放着 tt 的格子集合，8 邻域预计算成掩码，合法格子 = 未换过、自身非 tt、邻域无 tt。两个关键观察：每个格子恰好换一次且换入字母必不等于该格原字母，所以剩余需求由当前棋盘唯一推出，记忆化只需以棋盘编码（每格 3 bit 共 48 bit）为键；安全约束只看执行时刻的棋盘，相同棋盘的子树只展开一次。扩展顺序固定为字母升序 × 格子升序（第一步只有 D），深度优先走到的第一个完整叶子就是字典序最小方案，计数则继续展开所有分支。

参考代码

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 08:44
# update_at: 2026-10-01 08:44

import sys
from functools import cache

ROWS = COLS = 4
CELLS = ROWS * COLS
FULL = (1 << CELLS) - 1         # 16 个格子的全集（位掩码）
NEED = (3, 3, 3, 4, 3)          # 需求：A*3 B*3 C*3 D*4 E*3
# NB[i]：第 i 号格的 8 邻域（不含自身）
NB = tuple(
    sum(1 << (r2 * COLS + c2)
        for r2 in range(r - 1, r + 2) for c2 in range(c - 1, c + 2)
        if 0 <= r2 < ROWS and 0 <= c2 < COLS and (r2 != r or c2 != c))
    for r in range(ROWS) for c in range(COLS)
)

memo: dict[int, int] = {}  # 棋盘位编码 -> 从该状态能完成的搬运序列数


@cache
def zone(mask: int) -> int:
    """mask 覆盖的格子们的 8 邻域并集（位掩码），逐低位移除递归累加。"""
    return 0 if mask == 0 else zone(mask & (mask - 1)) | NB[(mask & -mask).bit_length() - 1]


def dfs(step: int, g: int, used: int, occ: list[int], left: list[int],
        path: list[tuple[int, int]], best: list[tuple[int, int]]) -> int:
    """返回当前棋盘能完成的搬运序列总数；字典序扩展保证首个叶子即最小解，存入 best。"""
    if step == CELLS:
        if not best:
            best.extend(path)
        return 1
    cached = memo.get(g)
    if cached is not None:      # 已算过的状态直接复用结果
        return cached
    cnt = 0
    for t in ((3,) if step == 0 else range(5)):  # 第 0 步必须搬 D
        if not left[t]:
            continue
        avail = FULL & ~(used | occ[t] | zone(occ[t]))  # 未被占用且 8 邻域无 t 的空格
        x = avail
        while x:
            b = x & -x
            x ^= b
            i = b.bit_length() - 1
            old = (g >> (3 * i)) & 7
            occ[old] ^= b  # 原住客 old 装上卡车离开
            occ[t] |= b    # 新奶牛 t 入住该格
            left[t] -= 1
            path.append((t, i))
            cnt += dfs(step + 1, g ^ ((t ^ old) << (3 * i)), used | b, occ, left, path, best)
            path.pop()
            left[t] += 1
            occ[t] &= ~b
            occ[old] |= b
    memo[g] = cnt
    return cnt


def solve() -> None:
    data = iter(b"".join(sys.stdin.buffer.read().split()))
    # 棋盘编码：每个格子 3 bit 存字母编号（0=A..4=E），兼容带/不带空格
    g = sum((next(data) - 65) << (3 * i) for i in range(CELLS))
    occ = [0] * 5  # occ[t]：当前放着 t 型奶牛的格子集合
    for i in range(CELLS):
        occ[(g >> (3 * i)) & 7] |= 1 << i
    path: list[tuple[int, int]] = []
    best: list[tuple[int, int]] = []
    total = dfs(0, g, 0, occ, list(NEED), path, best)
    out = [f"{'ABCDE'[t]} {i // COLS + 1} {i % COLS + 1}" for t, i in best]
    out.append(str(total))
    sys.stdout.write("\n".join(out) + "\n")


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 10:45
 * update_at: 2026-10-06 10:45
 */

// usaco 5.2.3 威斯康星州的牧场：
// 回溯搜索 + 位掩码 + 记忆化。
// 关键观察：每个格子恰好换一次，且换入字母必不等于该格原字母，
// 所以"已换的格子 / 各字母剩余需求"都由当前棋盘唯一决定，
// 记忆化只需要以棋盘编码为键；字母升序 x 格子升序扩展，
// 深度优先的第一个完整叶子就是字典序最小的方案。

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

const int NEED[5] = {3, 3, 3, 4, 3}; // 每种字母要搬进的小奶牛群数

int nbMask[16];   // nbMask[i]：格子 i 的 8 邻域（含对角线，不含自身）位掩码
int occ[5];       // occ[t]：当前放着字母 t 的格子集合
int leftCnt[5];   // leftCnt[t]：还差多少群 t 型小奶牛没搬进来
int usedMask;     // 已经换过奶牛的格子集合（每个格子只能换一次）
ll boardCode;     // 棋盘编码：每个格子用 3 bit 存字母编号 0..4，共 48 bit
map<ll, ll> memo; // memo[棋盘编码] = 从该棋盘出发能完成的合法搬运序列数

int pathT[16];    // 当前搜索路径：第 step 步放的字母编号
int pathCell[16]; // 当前搜索路径：第 step 步放的格子编号
int ansT[16];     // 答案方案：每步放的字母编号
int ansCell[16];  // 答案方案：每步放的格子编号
bool hasAns = false;

// 第一次走到的完整叶子就是字典序最小的方案，把它抄进答案数组
void recordAnswer() {
    for (int i = 0; i < 16; i++) {
        ansT[i] = pathT[i];
        ansCell[i] = pathCell[i];
    }
    hasAns = true;
}

// 返回从当前棋盘出发能完成的合法搬运序列总数
ll dfs(int step) {
    if (step == 16) { // 16 步全部走完，得到一个完整方案
        if (!hasAns) recordAnswer();
        return 1;
    }
    map<ll, ll>::iterator it = memo.find(boardCode);
    if (it != memo.end()) return it->second; // 相同棋盘只展开一次
    ll cnt = 0;
    // 第 0 步必须先搬 D；其余步按字母升序枚举，配合格子升序保证字典序最小
    int tBegin = (step == 0 ? 3 : 0);
    int tEnd = (step == 0 ? 3 : 4);
    for (int t = tBegin; t <= tEnd; t++) {
        if (leftCnt[t] == 0) continue; // 这种字母已经搬够
        for (int i = 0; i < 16; i++) { // 格子按行主序升序枚举
            int bit = 1 << i;
            if (usedMask & bit) continue;     // 该格已经换过
            if (occ[t] & bit) continue;       // 该格当前就是 t，不能放
            if (nbMask[i] & occ[t]) continue; // 8 邻域里有 t，不能放
            int old = (boardCode >> (3 * i)) & 7; // 该格当前住的字母
            boardCode ^= (ll)(t ^ old) << (3 * i); // 换入 t：翻转该格 3 bit
            occ[old] ^= bit;
            occ[t] |= bit;
            leftCnt[t]--;
            usedMask |= bit;
            pathT[step] = t;
            pathCell[step] = i;
            cnt += dfs(step + 1);
            usedMask &= ~bit; // 回溯，恢复现场
            leftCnt[t]++;
            occ[t] &= ~bit;
            occ[old] |= bit;
            boardCode ^= (ll)(t ^ old) << (3 * i);
        }
    }
    memo[boardCode] = cnt; // boardCode 已恢复到进入时的值
    return cnt;
}

int main() {
    // 预处理每个格子的 8 邻域位掩码
    for (int r = 0; r < 4; r++) {
        for (int c = 0; c < 4; c++) {
            int mask = 0;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    int r2 = r + dr, c2 = c + dc;
                    if (r2 < 0 || r2 >= 4 || c2 < 0 || c2 >= 4) continue;
                    if (r2 == r && c2 == c) continue;
                    mask |= 1 << (r2 * 4 + c2);
                }
            }
            nbMask[r * 4 + c] = mask;
        }
    }
    // 读入初始棋盘：四行，每行一个 4 字母的字符串
    for (int i = 0; i < 16; i++) {
        char ch;
        cin >> ch;
        int t = ch - 'A';
        boardCode |= (ll)t << (3 * i);
        occ[t] |= 1 << i;
    }
    for (int t = 0; t < 5; t++) leftCnt[t] = NEED[t];

    ll total = dfs(0);

    // 输出字典序最小的 16 步方案（字母 行 列，行列从 1 开始）和方案总数
    for (int i = 0; i < 16; i++) {
        printf("%c %d %d\n", 'A' + ansT[i], ansCell[i] / 4 + 1, ansCell[i] % 4 + 1);
    }
    printf("%lld\n", total);
    return 0;
}