转自：http://blog.csdn.net/qq_34594236/article/details/61209276
这个题有几个地方可以借鉴，给格子的编号，判断连通性等地方。
题目描述：
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
题目答案：
116
题目思路：
枚举五种数的所有组合然后判断这五个数是否连通即可。判断连通性可以用DFS来判断，上下左右四个方向可以将题目中的1，2，3，4，5，6，7，8，9，10数字进行转换，4和5是无法连通的，可以将其变为1，2，3，4，6，7，8，9，11，12，13，14如图，这样我就可以实现左右分别+1和-1，上下分别+5和-5来实现。
题目JAVA代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| public class 剪邮票
{
static int[] data=new int[]{1,2,3,4,6,7,8,9,11,12,13,14};
static int[] arr=new int[5];
static int[] vis=new int[5];
static int[] dir=new int[]{1,-1,5,-5};
static int ans=0;
public static void main(String[] args) {
for (int a = 0; a < data.length; a++) {
for (int b = a+1; b < data.length; b++) {
for (int c = b+1; c < data.length; c++) {
for (int d = c+1; d < data.length; d++) {
for (int e = d+1; e < data.length; e++) {
arr[0]=data[a];
arr[1]=data[b];
arr[2]=data[c];
arr[3]=data[d];
arr[4]=data[e];
vis=new int[5];
vis[0]=1;
dfs(0);
boolean fal=true;
for (int i = 0; i < 5; i++) {
if(vis[i]==0)
fal=false;
}
if(fal){
ans++;
// for (int i = 0; i < arr.length; i++) {
// System.out.print(arr[i]+" ");
// }
// System.out.println();
// for (int i = 0; i < arr.length; i++) {
// System.out.print(vis[i]+" ");
// }
// System.out.println();
}
}
}
}
}
}
System.out.println(ans);
}
//判断连通性
private static void dfs(int u) {
for(int i=0 ;i<4 ;i++){
int t = arr[u]+dir[i];
if(t>=1&&t<=14){
for(int j=0 ;j<5 ;j++)
if(t==arr[j]&&vis[j]==0){
vis[j]=1;
dfs(j);
}
}
}
}
}
|