蓝桥杯 国赛 矩阵计数 DFS

问题描述

一个 N × M 的方格矩阵，每一个方格中包含一个字符 O 或者字符 X。
要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。
问这样的矩阵一共有多少种？
【输入格式】
输入一行包含两个整数 N 和 M。
【输出格式】
输出一个整数代表答案。
【样例输入】

2 3
1
【样例输出】

49
1
【数据规模与约定】
对于所有评测用例，1 ≤ N, M ≤ 5。
 

Java 

import java.util.Scanner;

public class 矩阵计数 {
    static int n;
    static int m;
    static int[][] map;
    static int ans = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        map = new int[n][m];
        dfs(0,0);
        System.out.println(ans);
    }
    public static void dfs(int i,int j){
        //程序已经执行到了第n行，数组下标最大为n-1
        if(i == n){
            ans++;
            return;
        }
        //判断能否将当前位置插入一个1
        if(judge(i,j)){
            map[i][j] = 1;
            if(j < m - 1){
                dfs(i,j + 1);
            }else {
                //程序执行到此处说明当前行的全部位置都执行完了，执行下一行，从第一个开始
                dfs(i + 1,0);
            }
            map[i][j] = 0;
        }
        //当前位置不能插入一个1，那就跳过当前位置，执行下一个位置
        if(j < m - 1){
            dfs(i,j + 1);
        }else {
            dfs(i + 1,0);
        }
    }
    //要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X
    public static boolean judge(int i,int j){
        //行数都没有3，那就不用谈连续三个了
        if(n > 2 && i >= 2){
            if(map[i - 1][j] == map[i - 2][j] && map[i - 1][j] == 1){
                return false;
            }
        }
        if(m > 2 && j >= 2){
            if(map[i][j - 1] == map[i][j - 2] && map[i][j - 1] == 1){
                return false;
            }
        }
        return true;
    }
}