如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
不能边标记边判断，比如 2 3 4 5 6的情况，如果边标记边判断，确定了2 3 4之后，确定5，发现5不与其他的相邻，就不会继续往下走到6了。
但是仅仅深搜一边确定周围相邻也是不行的，比如
所以还是要确定之后再判断一次图是否连通
上代码，借鉴的一位博主的想法
public class test {
public static int count, t;
public static int[][] book = new int[6][6];
public static int[] num = new int[5];
public static int[] x = new int[] { 1, 0, -1, 0 };
public static int[] y = new int[] { 0, 1, 0, -1 };
public static void dfs1(int sx, int sy) {
for (int i = 0; i < 4; ++i) {
int ex = sx + x[i];
int ey = sy + y[i];
if (ex < 1 || ex > 3 || ey < 1 || ey > 4)
continue;
if (book[ex][ey] == 1) {
++t;
book[ex][ey] = 0;
dfs1(ex, ey);
}
}
}
public static void dfs(int i, int j) {
if (i == 5) {
for (int ii = 0; ii < 6; ++ii) {
for (int jj = 0; jj < 6; ++jj) {
book[ii][jj] = 0; // 避免上一步的残留
}
}
int sx = 0, sy = 0;
for (int k = 0; k < 5; ++k) {
sy = num[k] % 4;
if (sy == 0) {
sy = 4;
sx = num[k] / 4;
} else {
sx = num[k] / 4 + 1;
}
book[sx][sy] = 1;
}
t = 1;
book[sx][sy] = 0; // 从最后一个点查找,算第一步了
dfs1(sx, sy); // 5个点是否连通，走迷宫
if (t == 5) {
++count;
t = 0;
}
} else {
for (; j < 13; ++j) {
num[i] = j;
dfs(i + 1, j + 1);
}
}
}
public static void main(String[] args) {
dfs(0, 1);
System.out.println(count);
}
}========================================Talk is cheap, show me the code=======================================
京公网安备 11010502036488号