P1123 取数游戏

May 9, 2026 · 8 分钟阅读 · 深度优先搜索回溯枚举 ·

文章目录

题目信息

字段	内容
题号	P1123
难度	普及
知识点	深度优先搜索、回溯算法、状态标记

题目描述

在一个 n × m 的矩阵中，每个格子里有一个正整数。现在需要从中选取若干个数，要求任意两个被选的数在矩阵中不能相邻（包括上下左右和对角线共 8 个方向）。求能够选取的数的最大总和。

输入输出格式

输入格式：

第一行一个整数 T，表示测试用例数量
每个测试用例：
- 第一行两个整数 n 和 m
- 接下来 n 行，每行 m 个整数，表示矩阵

输出格式：

每个测试用例输出一行，表示最大总和

样例

输入：

输出：

解释： 选择 9、7、5、3、1，总和为 25。

解题思路

核心思想

这道题是一道典型的 DFS + 回溯 搜索题。

对于每个格子，我们有两种选择：

不选这个格子，直接搜索下一个
选这个格子（如果它的 8 个邻格都没有被选），然后标记这 8 个邻格为"不可用"，继续搜索

用 f[x][y] 表示位置 (x, y) 是否可以被选择（0 表示可选，>0 表示被占用）。

搜索策略

采用 按行优先 的顺序搜索：

从 (1, 1) 开始，依次搜索每个格子
当列号超过 m 时，换到下一行
当行号超过 n 时，说明所有格子都处理完了，更新答案

状态标记技巧

用一个巧妙的方法标记占用：

选择 (x, y) 时，将其 8 个邻格的 f 值 +1
回溯时，将这 8 个邻格的 f 值 -1
这样 f[x][y] == 0 就表示该格子可选

这种方法避免了每次选择时都要检查 8 个方向的麻烦。

完整代码

C++

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

int T, n, m;
int a[8][8];     // 存储矩阵
int f[8][8];     // 标记数组，f[x][y] > 0 表示不可用
int ans;          // 当前总和
int maxn;         // 最大总和

// 8 个方向：下、右下、右、右上、上、左上、左、左下
const int xx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int yy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

/**
 * DFS 回溯搜索
 * @param x 当前行号
 * @param y 当前列号
 */
void dfs(int x, int y) {
    // 列号越界，换到下一行第一列
    if (y == m + 1) {
        dfs(x + 1, 1);
        return;
    }
    // 行号越界，说明搜索完毕，更新答案
    if (x == n + 1) {
        maxn = max(ans, maxn);
        return;
    }
    
    // 选择 1：不选当前格子
    dfs(x, y + 1);
    
    // 选择 2：选当前格子（如果可选）
    if (f[x][y] == 0) {
        ans += a[x][y];  // 加上当前数
        
        // 标记 8 个邻格为不可用
        for (int i = 0; i < 8; i++) {
            int nx = x + xx[i];
            int ny = y + yy[i];
            f[nx][ny]++;
        }
        
        // 继续搜索
        dfs(x, y + 1);
        
        // 回溯：恢复 8 个邻格的状态
        for (int i = 0; i < 8; i++) {
            int nx = x + xx[i];
            int ny = y + yy[i];
            f[nx][ny]--;
        }
        
        // 回溯：减去当前数
        ans -= a[x][y];
    }
}

int main() {
    cin >> T;
    while (T--) {
        // 多测试用例，清空数组
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));
        
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        
        maxn = 0;
        ans = 0;
        dfs(1, 1);  // 从 (1, 1) 开始搜索
        
        cout << maxn << endl;
    }
    return 0;
}

关键代码讲解

1. 方向数组

const int xx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int yy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

这 8 个方向覆盖了当前格子的所有邻居（包括对角线）。

2. 状态标记与回溯

// 选择当前格子时，标记邻居
for (int i = 0; i < 8; i++) {
    int nx = x + xx[i];
    int ny = y + yy[i];
    f[nx][ny]++;
}

// 回溯时，恢复邻居状态
for (int i = 0; i < 8; i++) {
    int nx = x + xx[i];
    int ny = y + yy[i];
    f[nx][ny]--;
}

使用计数器而不是布尔值，可以正确处理多个格子同时影响同一个邻居的情况。

3. 搜索顺序

if (y == m + 1) {
    dfs(x + 1, 1);
    return;
}

按行优先搜索，保证每个格子都被考虑到。

复杂度分析

方法	时间复杂度	空间复杂度
DFS + 回溯	O(2^(n×m)) 最坏情况	O(n×m)

注意： 虽然最坏时间复杂度是指数级的，但由于：

每个格子只有"选"和"不选"两种状态
“选"的状态受到相邻限制，实际搜索空间远小于 2^(n×m)
n 和 m 最大为 6，实际运行很快

易错点

数组越界：标记邻居时，nx 和 ny 可能超出数组范围，但题目中 n, m ≤ 6，数组开到 8×8 并使用全局变量（自动初始化为 0），可以避免越界问题。
多测试用例清空：每次测试前要清空数组 a 和 f，否则上一组数据会影响结果。
回溯要完整：选择格子后，既要恢复邻居的标记，也要减去当前值。
搜索终止条件：当 x == n + 1 时才更新答案，而不是 x == n && y == m + 1。

优化建议

如果 n 和 m 更大，可以考虑：

状态压缩 DP：每一行用二进制表示选择状态，转移时检查与上一行的冲突
剪枝优化：如果当前 ans 加上剩余所有正数都小于 maxn，可以提前返回

其他语言解法

Java

import java.io.BufferedInputStream;
import java.io.InputStream;
import java.util.StringTokenizer;

/**
 * P1123 取数游戏 - Java 解法
 * 注意：洛谷禁止使用 Scanner，必须使用 FastScanner 避免 MLE
 */
public class Main {
    static int T, n, m;
    static int[][] a = new int[8][8];
    static int[][] f = new int[8][8];
    static int ans;
    static int maxn;
    
    // 8 个方向：下、右下、右、右上、上、左上、左、左下
    static int[] xx = {1, 1, 0, -1, -1, -1, 0, 1};
    static int[] yy = {0, 1, 1, 1, 0, -1, -1, -1};
    
    /**
     * DFS 回溯搜索
     * @param x 当前行号
     * @param y 当前列号
     */
    static void dfs(int x, int y) {
        // 列号越界，换到下一行第一列
        if (y == m + 1) {
            dfs(x + 1, 1);
            return;
        }
        // 行号越界，说明搜索完毕，更新答案
        if (x == n + 1) {
            maxn = Math.max(ans, maxn);
            return;
        }
        
        // 选择 1：不选当前格子
        dfs(x, y + 1);
        
        // 选择 2：选当前格子（如果可选）
        if (f[x][y] == 0) {
            ans += a[x][y];  // 加上当前数
            
            // 标记 8 个邻格为不可用
            for (int i = 0; i < 8; i++) {
                int nx = x + xx[i];
                int ny = y + yy[i];
                f[nx][ny]++;
            }
            
            // 继续搜索
            dfs(x, y + 1);
            
            // 回溯：恢复 8 个邻格的状态
            for (int i = 0; i < 8; i++) {
                int nx = x + xx[i];
                int ny = y + yy[i];
                f[nx][ny]--;
            }
            
            // 回溯：减去当前数
            ans -= a[x][y];
        }
    }
    
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        T = sc.nextInt();
        
        while (T-- > 0) {
            // 多测试用例，清空数组
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    a[i][j] = 0;
                    f[i][j] = 0;
                }
            }
            
            n = sc.nextInt();
            m = sc.nextInt();
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    a[i][j] = sc.nextInt();
                }
            }
            
            maxn = 0;
            ans = 0;
            dfs(1, 1);
            System.out.println(maxn);
        }
    }
    
    /**
     * 快速输入类（避免 Scanner 导致 MLE）
     */
    static class FastScanner {
        private BufferedInputStream bis = new BufferedInputStream(System.in);
        private byte[] buffer = new byte[1024];
        private int current = 0;
        private int size = 0;
        
        private int read() throws Exception {
            if (current >= size) {
                size = bis.read(buffer);
                current = 0;
                if (size <= 0) return -1;
            }
            return buffer[current++];
        }
        
        public int nextInt() throws Exception {
            int c = read();
            while (c <= ' ') c = read();
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int result = 0;
            do {
                result = result * 10 + (c - '0');
            } while ((c = read()) >= '0' && c <= '9');
            return result * sign;
        }
    }
}

Go

package main

import (
	"fmt"
)

// 全局变量
var (
	T, n, m     int
	a, f         [8][8]int
	ans, maxn   int
)

// 8 个方向：下、右下、右、右上、上、左上、左、左下
var xx = [8]int{1, 1, 0, -1, -1, -1, 0, 1}
var yy = [8]int{0, 1, 1, 1, 0, -1, -1, -1}

// dfs 执行 DFS 回溯搜索
// 参数：
//   x: 当前行号
//   y: 当前列号
func dfs(x, y int) {
	// 列号越界，换到下一行第一列
	if y == m+1 {
		dfs(x+1, 1)
		return
	}
	// 行号越界，说明搜索完毕，更新答案
	if x == n+1 {
		if ans > maxn {
			maxn = ans
		}
		return
	}

	// 选择 1：不选当前格子
	dfs(x, y+1)

	// 选择 2：选当前格子（如果可选）
	if f[x][y] == 0 {
		ans += a[x][y] // 加上当前数

		// 标记 8 个邻格为不可用
		for i := 0; i < 8; i++ {
			nx := x + xx[i]
			ny := y + yy[i]
			f[nx][ny]++
		}

		// 继续搜索
		dfs(x, y+1)

		// 回溯：恢复 8 个邻格的状态
		for i := 0; i < 8; i++ {
			nx := x + xx[i]
			ny := y + yy[i]
			f[nx][ny]--
		}

		// 回溯：减去当前数
		ans -= a[x][y]
	}
}

func main() {
	fmt.Scan(&T)
	for T > 0 {
		T--

		// 多测试用例，清空数组
		for i := 0; i < 8; i++ {
			for j := 0; j < 8; j++ {
				a[i][j] = 0
				f[i][j] = 0
			}
		}

		fmt.Scan(&n, &m)
		for i := 1; i <= n; i++ {
			for j := 1; j <= m; j++ {
				fmt.Scan(&a[i][j])
			}
		}

		maxn = 0
		ans = 0
		dfs(1, 1)
		fmt.Println(maxn)
	}
}

JavaScript

'use strict';

/**
 * P1123 取数游戏 - JavaScript 解法
 * 使用 Node.js 读取标准输入
 */

// 8 个方向：下、右下、右、右上、上、左上、左、左下
const XX = [1, 1, 0, -1, -1, -1, 0, 1];
const YY = [0, 1, 1, 1, 0, -1, -1, -1];

/** @type {number} */
let T, n, m;
/** @type {number[][]} */
let a = Array(8).fill(0).map(() => Array(8).fill(0));
/** @type {number[][]} */
let f = Array(8).fill(0).map(() => Array(8).fill(0));
/** @type {number} */
let ans;
/** @type {number} */
let maxn;

/**
 * DFS 回溯搜索
 * @param {number} x - 当前行号
 * @param {number} y - 当前列号
 */
function dfs(x, y) {
    // 列号越界，换到下一行第一列
    if (y === m + 1) {
        dfs(x + 1, 1);
        return;
    }
    // 行号越界，说明搜索完毕，更新答案
    if (x === n + 1) {
        maxn = Math.max(ans, maxn);
        return;
    }
    
    // 选择 1：不选当前格子
    dfs(x, y + 1);
    
    // 选择 2：选当前格子（如果可选）
    if (f[x][y] === 0) {
        ans += a[x][y];  // 加上当前数
        
        // 标记 8 个邻格为不可用
        for (let i = 0; i < 8; i++) {
            const nx = x + XX[i];
            const ny = y + YY[i];
            f[nx][ny]++;
        }
        
        // 继续搜索
        dfs(x, y + 1);
        
        // 回溯：恢复 8 个邻格的状态
        for (let i = 0; i < 8; i++) {
            const nx = x + XX[i];
            const ny = y + YY[i];
            f[nx][ny]--;
        }
        
        // 回溯：减去当前数
        ans -= a[x][y];
    }
}

/**
 * 主函数 - 处理输入并调用搜索
 */
function main() {
    const fs = require('fs');
    const data = fs.readFileSync(0, 'utf-8').trim().split(/\s+/).map(Number);
    
    let idx = 0;
    T = data[idx++];
    
    for (let t = 0; t < T; t++) {
        // 多测试用例，清空数组
        for (let i = 0; i < 8; i++) {
            for (let j = 0; j < 8; j++) {
                a[i][j] = 0;
                f[i][j] = 0;
            }
        }
        
        n = data[idx++];
        m = data[idx++];
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= m; j++) {
                a[i][j] = data[idx++];
            }
        }
        
        maxn = 0;
        ans = 0;
        dfs(1, 1);
        console.log(maxn);
    }
}

main();

类似题目

P1219 八皇后：经典的回溯问题
P2036 [COCI 2008/2009 #2] PERKET：DFS + 背包思想