题目描述
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
解题思路
使用暴力枚举,从 12 个格子中枚举出 5 个格子,然后判断这 5 个格子是否连通,判断连通可以用 DFS
参考代码
import java.util.*;
public class Main {
static boolean[] book = new boolean[13];
static int[] path = new int[5];
static int[][] map = new int[3][4];
static Set<String> set = new HashSet<String>();
static int ans;
public static void main(String[] args) {
dfs(0);
System.out.println(ans);
}
static void dfs(int idx) {
if (idx == 5) {
int[] tmp = Arrays.copyOf(path, 5);
Arrays.sort(tmp);
String str = tmp[0] + "" + tmp[1] + "" + tmp[2] + "" + tmp[3] + "" + tmp[4];
if (!set.contains(str) && check()) {
set.add(str);
System.out.println(str);
ans++;
}
} else {
for (int i = 1; i <= 12; i++) {
if (!book[i]) {
book[i] = true;
path[idx] = i;
dfs(idx + 1);
book[i] = false;
}
}
}
}
static boolean check() {
map = new int[4][5];
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 4; j++)
for (int t = 0; t < 5; t++)
if ((i - 1) * 4 + j == path[t])
map[i][j] = 1;
// dfs check connected
int cnt = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 4; j++)
if (map[i][j] == 1) {
dfs_connect(i, j);
cnt++;
}
return cnt == 1;
}
static void dfs_connect(int i, int j) {
map[i][j] = 0;
if (i + 1 <= 3 && map[i + 1][j] == 1) dfs_connect(i + 1, j);
if (j + 1 <= 4 && map[i][j + 1] == 1) dfs_connect(i, j + 1);
if (i - 1 >= 1 && map[i - 1][j] == 1) dfs_connect(i - 1, j);
if (j - 1 >= 1 && map[i][j - 1] == 1) dfs_connect(i, j - 1);
}
}
答案
116