剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。
仅仅连接一个角不算相连，比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
解题思路：遍历每一种可能的五个数字的组合，用广度优先遍历检验这五个数字是否连通。
1 #include<iostream>
2 #include<deque>
3 #include<stdio.h>
4 #include<memory.h>
5 using namespace std;
6 struct point
7 {
8 int x;
9 int y;
10 };
11
12 int main()
13 {
14 int sum=0;
15 int loc[5];
16 for( loc[0]=1;loc[0]<=8;loc[0]++)
17 for( loc[1]=loc[0]+1;loc[1]<=9;loc[1]++)
18 for(loc[2]=loc[1]+1;loc[2]<=10;loc[2]++)
19 for( loc[3]=loc[2]+1;loc[3]<=11;loc[3]++)
20 for( loc[4]=loc[3]+1;loc[4]<=12;loc[4]++)
21 {
22 /* 将选出的五个数字转到二维数组中，选中位置置为1，未选中位置置为0 */
23 int a[4][13];
24 memset(a,0,sizeof(a));
25 int x,y;
26 for(int i=0;i<5;i++)
27 {
28 if(loc[i]%4==0)
29 {
30 x=loc[i]/4-1;
31 y=3;
32 }
33 else
34 {
35 x=loc[i]/4;
36 y=loc[i]%4-1;
37 }
38
39 a[x][y]=1;
40 }
41 int ans=0; //ans为连接的数量
42 int book[4][13]; //用于将来队列广度遍历时记录当前位置是否用过
43 memset(book,0,sizeof(book));
44 point pos;
45 pos.x=x;
46 pos.y=y;
47 book[x][y]=1; // 标志该位置已经被遍历到了
48 deque<point> ql;
49 ql.push_back(pos);
50 ans++;
51 while(!ql.empty())
52 {
53 /* 计算四个方向上是否有连通且未被遍历到的元素 */
54 if(a[ql[0].x-1][ql[0].y]&&(ql[0].x-1)>=0&&book[ql[0].x-1][ql[0].y]==0)//up
55 {
56 book[ql[0].x-1][ql[0].y]=1;
57 pos.x=ql[0].x-1;
58 pos.y=ql[0].y;
59 ql.push_back(pos); //将新的元素加入到队列中去
60 ans++;
61 }
62 if(a[ql[0].x+1][ql[0].y]&&(ql[0].x+1)<=2&&book[ql[0].x+1][ql[0].y]==0)//down
63 {
64 book[ql[0].x+1][ql[0].y]=1;
65 pos.x=ql[0].x+1;
66 pos.y=ql[0].y;
67 ql.push_back(pos);
68 ans++;
69 }
70 if(a[ql[0].x][ql[0].y+1]&&(ql[0].y+1)<=3&&book[ql[0].x][ql[0].y+1]==0)//r
71 {
72 book[ql[0].x][ql[0].y+1]=1;
73 pos.x=ql[0].x;
74 pos.y=ql[0].y+1;
75 ql.push_back(pos);
76 ans++;
77 }
78 if(a[ql[0].x][ql[0].y-1]&&(ql[0].y-1)>=0&&book[ql[0].x][ql[0].y-1]==0)//l
79 {
80 book[ql[0].x][ql[0].y-1]=1;
81 pos.x=ql[0].x;
82 pos.y=ql[0].y-1;
83 ql.push_back(pos);
84 ans++;
85 }
86 ql.pop_front();
87
88 }
89 if(ans==5)
90 {
91 sum++;
92 }
93
94 }
95
96 cout<<sum;
97 getchar();
98 return 0;
99 }