P1123 取数游戏 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1123，日期见页头。两边不一致时信原站。

题目描述

一个 N × M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个，即认为这两个数字相邻），求取出数字和最大是多少。

输入格式：第一行有一个正整数 T，表示了有 T 组数据。对于每一组数据，第一行有两个正整数 N 和 M，表示了数字矩阵为 N 行 M 列。接下来 N 行，每行 M 个非负整数，描述了这个数字矩阵。

输出格式：共 T 行，每行一个非负整数，输出所求得的答案。

数据范围：对于 20% 的数据，1 ≤ N, M ≤ 3；对于 40% 的数据，1 ≤ N, M ≤ 4；对于 60% 的数据，1 ≤ N, M ≤ 5；对于 100% 的数据，1 ≤ N, M ≤ 6，1 ≤ T ≤ 20，aᵢⱼ ≤ 10⁵。

样例解释：第一组数据的取数方式（方括号里的是取出来的）：

   [67]   75   63   10
    29    29  [92]  14
   [21]   68   71   56
    8     67  [91]  25

输入输出样例

输入

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

输出

271
172
99

三组数据的答案分别是 67 + 92 + 21 + 91 = 271、172、99。 上面那段输出是仓库里的 p1123.cpp 真跑出来的。

1先看清楚：这是「选或不选」，不是「每行选一个」

第 4 章的 N 皇后是每行恰好放一个，这道题不是 —— 每一格都可以选、也可以不选，一行里选几个都行（只要不挨着）。

   N 皇后：  dfs(第几行)      每层从 n 个列里挑一个
   这道题：  dfs(第几格)      每层只有两个分支：选 / 不选

★ 但回溯的骨架一模一样：进入（标记这一格选了）→ 递归 → 撤销。

⚠ 而这道题真正的坑不在骨架上，在两个更小的地方 —— 下面两步各是一个。

2第 ① 版：贪心 —— 从大到小挑，能选就选

「每次都拿当前最大的那个」是几乎所有人的第一反应。

p1123Greedy.cpp第 ① 版：贪心（错的）

★★ 三组样例它一个字都不差 —— 271 / 172 / 99，全对。

// ② 写错的版本：贪心 —— 从大到小挑，能选就选
//
// 「每次都拿当前最大的那个」是几乎所有人的第一反应，而它在这道题上是错的：
// 拿走一个大的，会把它周围八格全部作废，可那八格加起来可能更多。
//
// ★★ **样例挡不住它 —— 三组一个字都不差。**（正文第 ③ 步实测。）
//   而对拍第一组随机数据就把它打假了，那组只有 3 行 2 列：
//
//       6 0        贪心先拿 8，8 的八个邻居全废 ⇒ 只剩 8
//       1 8        正解拿 6 和 5（隔着一行，不相邻）⇒ 11
//       1 5
//
//   ⇒ 「拿走一个大的，会把它周围八格全部作废，而那八格加起来可能更多」——
//     这句话在样例上一次都没发生，在随机数据上第一组就发生了。

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[8][8];
bool pick[8][8];

bool ok(int r, int c) {
    for (int dr = -1; dr <= 1; dr++)
        for (int dc = -1; dc <= 1; dc++) {
            if (dr == 0 && dc == 0) continue;
            int nr = r + dr, nc = c + dc;
            if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
            if (pick[nr][nc]) return false;
        }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        vector<array<int, 3>> all;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) { cin >> a[i][j]; all.push_back({ a[i][j], i, j }); }
        sort(all.rbegin(), all.rend());          // 从大到小
        memset(pick, 0, sizeof(pick));
        long long sum = 0;
        for (auto& t : all)
            if (ok(t[1], t[2])) { pick[t[1]][t[2]] = true; sum += t[0]; }
        cout << sum << '\n';
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 样例挡不住它，而随机数据第一组就把它打假了

拿走一个大的，会把它周围八格全部作废，而那八格加起来可能更多。这件事在三组样例上一次都没发生，在随机小矩阵上第一组就发生了：

   6 0        贪心先拿 8 —— 它的八个邻居全废了 ⇒ 答案 8
   1 8
   1 5        正解拿 6 和 5（隔着一整行，不相邻）⇒ 答案 11

⇒ 「样例过了」什么都不说明。 这是这一系列解析里第五次遇到同一件事（前四次是 P1036 的 isPrime、P2036 的空集、 P1255 和 P1096 的溢出）。

★ 而这一次多了一个便宜的办法：对拍。300 轮随机小矩阵，它被抓 42 轮。

对拍器

轮数

生成器只造 1~4 行 1~4 列、每格 0~9 的小矩阵 —— ★ 这么随手的数据就够了，贪心 300 轮里错 42 轮。

// ② 写错的版本：贪心 —— 从大到小挑，能选就选
//
// 「每次都拿当前最大的那个」是几乎所有人的第一反应，而它在这道题上是错的：
// 拿走一个大的，会把它周围八格全部作废，可那八格加起来可能更多。
//
// ★★ **样例挡不住它 —— 三组一个字都不差。**（正文第 ③ 步实测。）
//   而对拍第一组随机数据就把它打假了，那组只有 3 行 2 列：
//
//       6 0        贪心先拿 8，8 的八个邻居全废 ⇒ 只剩 8
//       1 8        正解拿 6 和 5（隔着一行，不相邻）⇒ 11
//       1 5
//
//   ⇒ 「拿走一个大的，会把它周围八格全部作废，而那八格加起来可能更多」——
//     这句话在样例上一次都没发生，在随机数据上第一组就发生了。

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[8][8];
bool pick[8][8];

bool ok(int r, int c) {
    for (int dr = -1; dr <= 1; dr++)
        for (int dc = -1; dc <= 1; dc++) {
            if (dr == 0 && dc == 0) continue;
            int nr = r + dr, nc = c + dc;
            if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
            if (pick[nr][nc]) return false;
        }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        vector<array<int, 3>> all;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) { cin >> a[i][j]; all.push_back({ a[i][j], i, j }); }
        sort(all.rbegin(), all.rend());          // 从大到小
        memset(pick, 0, sizeof(pick));
        long long sum = 0;
        for (auto& t : all)
            if (ok(t[1], t[2])) { pick[t[1]][t[2]] = true; sum += t[0]; }
        cout << sum << '\n';
    }
    return 0;
}

点一下即可编辑

3第 ② 版：搜索对了，但「相邻」数错了

p1123Four.cpp第 ② 版：只当上下左右算相邻

它给 429 / 175 / 103，三组样例全错 —— 这一处样例挡得住。

// ① 写错的版本：只当上下左右四个方向算相邻，忘了四个斜角
//
// 题面写的是「若一个数在另外一个数相邻 8 个格子中的一个」—— **8 个**，含斜角。
// 这一版只查了「正上」和「正左」（按行优先走的话，四邻里排在前面的只有这两个），
// 于是它允许两个斜着挨着的数同时被选。
//
// ★ 这一处**样例就能挡住**，而且挡它的是**第三组**：
//     1 1 1
//     1 99 1
//     1 1 1
//   正确答案是 99（选了中间那个 99，八个邻居就全废了）；
//   这一版会选 99 加上四个角上的 1，给出 103。

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[8][8];
bool pick[8][8];
long long best, calls;

/** (r, c) 能不能选：只查已经决定过的那四个邻居 */
bool ok(int r, int c) {
    const int dr[2] = { -1, 0 };             // ⚠ 只有「正上」和「正左」
    const int dc[2] = { 0, -1 };
    for (int d = 0; d < 2; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nc < 0 || nc >= m) continue;
        if (pick[nr][nc]) return false;
    }
    return true;
}

void dfs(int idx, long long sum) {
    calls++;
    if (idx == n * m) { best = max(best, sum); return; }
    int r = idx / m, c = idx % m;
    dfs(idx + 1, sum);                       // ① 不选
    if (ok(r, c)) {                          // ② 选
        pick[r][c] = true;
        dfs(idx + 1, sum + a[r][c]);
        pick[r][c] = false;                  // ⚠ 撤销
    }
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) cin >> a[i][j];
        memset(pick, 0, sizeof(pick));
        best = 0;
        dfs(0, 0);
        cout << best << '\n';
    }
    if (argc > 1 && string(argv[1]) == "calls") cerr << "dfs 调用了 " << calls << " 次\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 挡住它的是第三组样例，而那一组是专门为它设计的

   1  1  1
   1 99  1
   1  1  1

正确答案是 99：选了中间那个 99，八个邻居就全废了。而只查四邻的版本会选 99 加上四个角，给出 103。

⇒ 出题人把「8 个格子」这句话做成了一组样例。 ★ 一般化：样例里那些看着「太特殊」的小数据，往往正是出题人替你准备的一处陷阱说明。

4第 ③ 版：一格一格问「选还是不选」

p1123.cpp第 ③ 版：回溯（能 AC）

// 推荐写法：一格一格地问「选还是不选」，选了就检查冲突，回来时撤销
//
// ★ 这就是第 4 章那套「进入 → 递归 → 撤销」，只是棋盘从「每行一个皇后」
//   变成了「每一格独立地选或不选」：
//
//       dfs(i) = 第 i 格不选 -> dfs(i+1)
//                第 i 格选   -> 标记、dfs(i+1)、★ 撤销标记
//
// ⚠ 冲突的定义是**八个方向**（含四个斜角），不是上下左右四个 ——
//   题面那句「相邻 8 个格子中的一个」就是这个意思，p1123Four.cpp 演示了漏掉斜角会怎样。
//
// ★ 只用往「前面」查：按行优先一格一格走，第 i 格的八个邻居里，
//   排在它前面的只有**左上、正上、右上、正左**这四个 —— 后面那四个还没决定，不用管。
//
// 输入：第一行 T；每组第一行 N M，接着 N 行 M 个非负整数。

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[8][8];
bool pick[8][8];
long long best, calls;

/** (r, c) 能不能选：只查已经决定过的那四个邻居 */
bool ok(int r, int c) {
    const int dr[4] = { -1, -1, -1, 0 };
    const int dc[4] = { -1, 0, 1, -1 };
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nc < 0 || nc >= m) continue;
        if (pick[nr][nc]) return false;
    }
    return true;
}

void dfs(int idx, long long sum) {
    calls++;
    if (idx == n * m) { best = max(best, sum); return; }
    int r = idx / m, c = idx % m;
    dfs(idx + 1, sum);                       // ① 不选
    if (ok(r, c)) {                          // ② 选
        pick[r][c] = true;
        dfs(idx + 1, sum + a[r][c]);
        pick[r][c] = false;                  // ⚠ 撤销
    }
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) cin >> a[i][j];
        memset(pick, 0, sizeof(pick));
        best = 0;
        dfs(0, 0);
        cout << best << '\n';
    }
    if (argc > 1 && string(argv[1]) == "calls") cerr << "dfs 调用了 " << calls << " 次\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

两个值得单说的地方：

★ 只用往「前面」查。 按行优先一格一格走，第 i 格的八个邻居里，排在它前面、已经决定过的只有 左上、正上、右上、正左 四个 —— 后面那四个还没决定，等轮到它们时自然会回头查这一格。 ⇒ 这就是为什么正解里的 ok() 只写了四个方向，而它和「八连通」一点都不矛盾。
⚠ 撤销不能忘（第 4 章那一课）：pick[r][c] = false。

本机实测（B 机：原生 Ubuntu / i5-10210U 8 线程 / 18 GB，2026-08-26，独占）：最坏情况（T = 20 组、每组 6 × 6）0.14 秒，题目限时 1 秒。

★★ 为什么 2 的 36 次方没有炸

6 × 6 有 36 格，每格选或不选 —— 光看这句话是 2³⁶ ≈ 687 亿 种。可实测一个 6 × 6 全 1 的矩阵，dfs 只被调用了 758 225 次，差 9 万倍。

⇒ 因为「选」这个分支只在不冲突时才走：选了一格，它右边和下面一圈就再也进不去了。 ★ 这正是第 4 章那句话的另一种说法：回溯的力气全花在「不合法就不往下走」上 —— 而这道题里，这一条剪枝不是优化，是题意本身。

这一页记住三句话

★★★ 贪心在三组样例上一个字都不差，随机数据第一组就打假了。 ⇒ 「拿最大的」在这类「选了就废掉一圈」的题里几乎总是错的，而证明它错最便宜的办法是对拍，不是想。
★ 「相邻 8 个格子」要数全 —— 出题人把这句话做成了第三组样例（99 那组）。
★ 按行优先走的话，ok() 只用查前面四个方向 —— 这不是偷懒，是「后面那四个还没决定」这件事的直接后果。

洛谷 P1123 取数游戏

0题目原文（本地存了一份）

输入

输出

1先看清楚：这是「选或不选」，不是「每行选一个」

2第 ① 版：贪心 —— 从大到小挑，能选就选

3第 ② 版：搜索对了，但「相邻」数错了

4第 ③ 版：一格一格问「选还是不选」