真题246—矩阵计数

真题246—矩阵计数

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+剪枝）来解决，原因如下：

1. 问题规模较小（N,M ≤ 5），回溯法在时间上是可行的
2. 需要枚举所有可能的矩阵配置
3. 可以在搜索过程中及时剪枝，排除不符合条件的配置

关键思路

1. 逐格填充：从矩阵左上角(0,0)开始，依次考虑每个格子填O还是X
2. 约束检查：
   • 当考虑填X时，检查当前格子左边两个是否都是X（防止行连续3个X）
   • 检查当前格子上方两个是否都是X（防止列连续3个X）
3. 回溯机制：
   • 尝试填X（如果满足条件）
   • 然后总是尝试填O的情况
   • 通过递归探索所有可能性

算法优化

1. 剪枝策略：在填充X前先检查是否违反规则，避免无效搜索
2. 状态表示：使用布尔二维数组，true表示X，false表示O
3. 遍历顺序：按行优先顺序遍历，处理完一行自动转到下一行开头

代码实现

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);
            else
                dfs(x + 1, 0);
            // 回溯：取消当前单元格的占用标记
            map[x][y] = false;
        }
        
        // 同时探索当前单元格保持空置的情况
        // 移动到下一个单元格：
        // 如果不在最后一列，则向右移动；否则移动到下一行的第一列
        if (y < m - 1)
            dfs(x, y + 1);
        else
            dfs(x + 1, 0);
    }
}

3.类似问题解决方法

适用场景

这种回溯+剪枝的方法适用于以下类型的问题：

1. 需要在网格或矩阵中填充元素
2. 有特定的相邻元素约束条件
3. 问题规模适中（通常N,M ≤ 10）

变种问题示例

1. 数独求解：9×9网格，需要满足行、列、宫格内的数字不重复
2. N皇后问题：在N×N棋盘放置N个皇后，互不攻击
3. 路径计数问题：在网格中从起点到终点的路径计数，可能有障碍物

通用解题步骤

1. 定义状态表示：选择合适的数据结构表示当前状态
2. 设计递归函数：参数通常包括当前位置和当前状态
3. 实现约束检查：在每次尝试新选择前检查是否满足条件
4. 实现回溯机制：尝试一个选择后要能撤销选择
5. 确定终止条件：明确何时统计一个有效解