真题246—矩阵计数
文章目录
- 真题246—矩阵计数
- 1.题目描述
- 输入描述
- 输出描述
- 输入输出样例
- 示例
- 2.解题思路
- 方法选择
- 关键思路
- 算法优化
- 代码实现
- 3.类似问题解决方法
- 适用场景
- 变种问题示例
- 通用解题步骤
1.题目描述
一个 N×M 的方格矩阵，每一个方格中包含一个字符 O 或者字符 X。
要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。
问这样的矩阵一共有多少种？
输入描述
输入一行包含两个整数 N,M (1≤N,M≤5)N,M (1≤N,M≤5)。
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
2 3
输出
49
2.解题思路
方法选择
本题采用回溯算法（DFS+剪枝）来解决，原因如下：
- 问题规模较小（N,M ≤ 5），回溯法在时间上是可行的
- 需要枚举所有可能的矩阵配置
- 可以在搜索过程中及时剪枝，排除不符合条件的配置
关键思路
- 逐格填充：从矩阵左上角(0,0)开始，依次考虑每个格子填O还是X
- 约束检查：
- 当考虑填X时，检查当前格子左边两个是否都是X（防止行连续3个X）
- 检查当前格子上方两个是否都是X（防止列连续3个X）
- 回溯机制：
- 尝试填X（如果满足条件）
- 然后总是尝试填O的情况
- 通过递归探索所有可能性
算法优化
- 剪枝策略：在填充X前先检查是否违反规则，避免无效搜索
- 状态表示：使用布尔二维数组，true表示X，false表示O
- 遍历顺序：按行优先顺序遍历，处理完一行自动转到下一行开头
代码实现
import java.util.Scanner;public class Main {// 静态变量声明：// n - 网格的行数// m - 网格的列数// ans - 统计有效摆放方式的数量// map - 二维布尔数组表示网格（true表示占用，false表示空置）static int n, m, ans = 0;static boolean[][] map;public static void main(String[] args) {// 初始化输入扫描器Scanner scan = new Scanner(System.in);// 读取网格尺寸n（行）和m（列）n = scan.nextInt();m = scan.nextInt();// 初始化网格，所有单元格默认为空置（false）map = new boolean[n][m];// 从左上角(0,0)开始深度优先搜索dfs(0, 0);// 输出找到的有效摆放方式总数System.out.println(ans);// 关闭扫描器scan.close();}// 深度优先搜索函数，用于探索所有可能的摆放方式static void dfs(int x, int y) {// 基准情况：如果已处理完所有行，计数增加并返回if (x == n) {ans++;return;}// 检查当前单元格(x,y)是否可以占用：// 1. 上方没有两个连续被占用的单元格（垂直检查）// 2. 左侧没有两个连续被占用的单元格（水平检查）if ((x < 2 || !map[x-1][y] || !map[x-2][y]) && (y < 2 || !map[x][y-1] || !map[x][y-2])) {// 标记当前单元格为占用状态map[x][y] = true;// 移动到下一个单元格：// 如果不在最后一列，则向右移动；否则移动到下一行的第一列if (y < m - 1)dfs(x, y + 1);elsedfs(x + 1, 0);// 回溯：取消当前单元格的占用标记map[x][y] = false;}// 同时探索当前单元格保持空置的情况// 移动到下一个单元格：// 如果不在最后一列，则向右移动；否则移动到下一行的第一列if (y < m - 1)dfs(x, y + 1);elsedfs(x + 1, 0);}
}
3.类似问题解决方法
适用场景
这种回溯+剪枝的方法适用于以下类型的问题：
- 需要在网格或矩阵中填充元素
- 有特定的相邻元素约束条件
- 问题规模适中（通常N,M ≤ 10）
变种问题示例
- 数独求解：9×9网格，需要满足行、列、宫格内的数字不重复
- N皇后问题：在N×N棋盘放置N个皇后，互不攻击
- 路径计数问题：在网格中从起点到终点的路径计数，可能有障碍物
通用解题步骤
- 定义状态表示：选择合适的数据结构表示当前状态
- 设计递归函数：参数通常包括当前位置和当前状态
- 实现约束检查：在每次尝试新选择前检查是否满足条件
- 实现回溯机制：尝试一个选择后要能撤销选择
- 确定终止条件：明确何时统计一个有效解