如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下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);
}
}
最后答案是116种