题目描述
一个 N×M 的方格矩阵,每一个方格中包含一个字符 O 或者字符 X。
要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。
问这样的矩阵一共有多少种?
输入描述
输入一行包含两个整数 N,M (1≤N,M≤5)。
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
2 3
输出
49
解题思路
考虑到每一个格子的位置只有两种状态,以及题目数据规模较小,可以考虑到状态压缩dp思路,也可以通过位运算配合dfs排列组合进行验证。
我们可以用位运算获得所有满足要求的行,即一行没有三个连续的1的所有情况,本题的关键也正是用位运算技巧代替X和O符号。
如果使用dfs配合排列组合验证,代码写起来就会比较简单:
import java.util.ArrayList;
import java.util.Scanner;
public class Main1 {
static int n, m;
static ArrayList<Integer> row;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
row = new ArrayList<>();
outer:
for (int i = 0; i < (1 << m); i++) {
int test = 7;
while (test <= i) {
if ((i & test) == test) {
continue outer;
}
test <<= 1;
}
row.add(i);
}
matrix = new int[n];
dfs(0);
System.out.println(ans);
}
static int[] matrix;
static int ans = 0;
static boolean check() {
for (int i = 0; i + 2 < n; i++) {
if ((matrix[i] & matrix[i + 1] & matrix[i + 2]) != 0) {
return false;
}
}
return true;
}
static void dfs(int s) {
if (s == n) {
if (check()) {
ans++;
}
return;
}
for (int e : row) {
matrix[s] = e;
dfs(s + 1);
}
}
}
如果使用状态压缩dp,对于这道题而言建模起来就比较有难度。
定义dp[i][j][k]为,当前为第i行时,本行的合法状态为j,前一行的合法状态为k时的排列数。
在循环计算中,我们内层循环需要编写3层,一次搜索3行的状态进行验证,即下面代码中的j、k、l分别表示三行的状态,最后将最后一行所有的状态的情况加起来,就是答案:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<Integer> row = new ArrayList<>();
outer:
for (int i = 0; i < (1 << m); i++) {
int test = 7;
while (test <= i) {
if ((i & test) == test) {
continue outer;
}
test <<= 1;
}
row.add(i);
}
int[][][] dp = new int[n][1 << m][1 << m];
for (int e : row) {
dp[0][e][0] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < row.size(); j++) {
for (int k = 0; k < row.size(); k++) {
for (int l = 0; l < row.size(); l++) {
if ((row.get(j) & row.get(k) & row.get(l)) == 0) {
dp[i][row.get(j)][row.get(k)] += dp[i - 1][row.get(k)][row.get(l)];
}
}
}
}
}
long ans = 0;
for (int i = 0; i < row.size(); i++) {
for (int j = 0; j < row.size(); j++) {
ans += dp[n - 1][row.get(i)][row.get(j)];
}
}
System.out.println(ans);
}
}