剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。请你计算，一共有多少种不同的剪取方法。
思路：先找到5个数的组合，然后从第一个数字开始遍历，经过上下左右操作检测5个数是否都被访问一遍，如果5个数都可以遍历到则种类+1。
在原图中向上为-4，向下为+4，向左为-1，向右为+1，但是遇到3 4 5 7 8这种4+1=5但是这种情况不符合，所以重构一下原图：
这样，向上为-5，向下为+5，向左为-1，向右为+1，避免了每行最后一个+1后等于下一行第一个的情况。
答案：116
[cpp] view plain copy #include <iostream> using namespace std; int mp[12]= {1,2,3,4,6,7,8,9,11,12,13,14}; int aa[5],vis[5],sum=0; int b[4]= {-1,1,-5,+5}; void dfs(int n) { for(int i=0; i<4; i++) { int t=aa[n]+b[i]; if(t<1||t>14||t==5||t==10) continue; for(int j=0; j<5; j++) if(!vis[j]&&aa[j]==t) { vis[j]=1; dfs(j); } } } int main() { for(int a=0; a<12; a++) for(int b=a+1; b<12; b++) for(int c=b+1; c<12; c++) for(int d=c+1; d<12; d++) for(int e=d+1; e<12; e++) { aa[0]=mp[a]; aa[1]=mp[b]; aa[2]=mp[c]; aa[3]=mp[d]; aa[4]=mp[e]; for(int i=0; i<5; i++) vis[i]=0; vis[0]=1; dfs(0); int flag=1;; for(int i=0; i<5; i++) { if(vis[i]!=1) { flag=0; break; } } if(flag==0) continue; else sum++; } cout<<sum<<endl; return 0; }
他的这个写法如果是在考场上，我实在是佩服，怎么说呢，这个方法很巧妙，用到了降维处理，在二维中的上下左右四种移动方式转化成了一维中的加减操作，这其实又回到了数组的本质，数组不管是几维的，其实他都是一维的，在计算机中是连续存储的。好了，我们做好降维处理之后，会出现一个问题，4+1=5，那么说明5是和4邻接的，这显然不对，发生这种情况的原因在于抽象的数据结构和数据在计算机中具体的形式之间的差异造成的，这不足为怪，这完全可以运用我们的智慧来完美解决，既然4+1=5不邻接，那么就让5+1不久OK了，我说的这么轻松，其实这一步才是这个解法的最核心的地方。
