不得不说蓝桥杯对全排列是情有独钟啊，一年考了三个全排列… 如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。
注意此题不能直接用DFS做(我就直接做的 )，不能做的原因是DFS不能处理"T"型，DFS只能在四个方向中选择一个走，不能同时走左和右多个方向。这样如图3的情况便不会得到。 其实暴力就完事了，暴力求解出12个块里边任选五个块，再用DFS求连通块的方法看这五个块是否连通，如果连通则此法符合题意。 那么该如何12个里选5个呢？ 要把所有的组合情况都考虑到，当然首选全排列啦，设置一个num数组，把选择此块记为1，不选记为0，然后对数组全排列即可。全排列后注意把num数组转化为地图的二维数组再去求连通块。 代码如下
#include <iostream> #include <string> #include <set> #include <vector> #include <algorithm> int mp[3][4]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int vis[3][4]; int cnt; int ans; void dfs(int x,int y)//求连通块 { if(x>2 || y>3 || x<0 || y<0 ) return; if(mp[x][y]!=1 )return; cnt ++;//连通的数目加一 if(cnt == 5)//如果连通的块数为5说明选择的五个点是连通的 { ans++; return; } mp[x][y] = 0;//此点连通后就标为0 for(int i=0;i<4;i++) { int dx = x+dir[i][0]; int dy = y+dir[i][1]; dfs(dx,dy); } } int main() { int px,py; int num []= {0,0,0,0,0,0,0,1,1,1,1,1};//通过全排列方式得到12个里选5个的选法 do { for(int i=0;i<3;i++) { for(int j=0;j<4;j++) { if(num[i*4+j]==1)//把num数组为1即代表选择此点，转化为二维数组体现 { px = i;//随便记录为1的一点，以这点开始连通块的搜索 py = j; mp[i][j] = 1; } else mp[i][j] = 0; } } dfs(px,py);//连通块搜索 cnt = 0;//搜索后数量记录置零 }while(next_permutation(num,num+12)); cout<<ans; }