本文共 1796 字，大约阅读时间需要 5 分钟。

题目描述：

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。

思路：用数组int b[] = {0,0,0,0,0,0,0,1,1,1,1,1}; 生成对应12个位置的全排列

dfs判断是否有5个1可以满足题目条件的连通方式                                                    

这里注意 设置已经访问的时刻 （这里是第一种）

（1）进去某个点即访问                                                                            

（2）判断下一个位置可行后设置访问过                                                         

1AC代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int row = 3;const int col = 4;bool vis[row][col];int map[row][col];int dir[4][2] = {
  {0,1},{0,-1},{-1,0},{1,0}};int ans;void dfs(int x, int y)	{		vis[x][y] = true;		for(int i = 0; i < 4; ++i){			int nx = x + dir[i][0];			int ny = y + dir[i][1];			if(nx<0||nx>=row || ny<0||ny>=col) continue;			if(vis[nx][ny] || !map[nx][ny]) continue;			//vis[nx][ny] = true;			dfs(nx,ny);		}	}int main()	{		int b[] = {0,0,0,0,0,0,0,1,1,1,1,1};		do{			memset(vis,false,sizeof(vis));			memset(map,0,sizeof(map));			int cnt = 0;			for(int i = 0; i < row; ++i){				for(int j = 0; j < col; ++j){					map[i][j] = b[cnt++];				}			}			int num = 0;			for(int i = 0; i < row; ++i){//这里就是判断连通分量个数 如果这5值为1的点为一个连通分量 则 满足条件				for(int j = 0; j < col; ++j){					if(!vis[i][j] && map[i][j]){						++num;					//	vis[i][j] = true;						dfs(i,j);					}				}			}			if(num == 1)//连通分量数为1 即5个位置连通				++ans;					}while(next_permutation(b,b+12));				cout <
      
     
    
   

2这个是错误答案：原本想通过dfs逐个判断累加个数除上5 但是 结果不对  也不知道为啥

#include
   
    #include
    
     #include
     
      using namespace std;const int row = 3;const int col = 4;int ans;int map[row][col];bool vis[row][col];int dir[4][2] = {
  {-1,0},{0,1},{1,0},{0,-1}};void dfs(int x,int y,int step)	{		if(step == 5){			++ans;			return ;		}				for(int i = 0; i < 4; ++i){			int nx = x + dir[i][0];			int ny = y + dir[i][1];			if(nx>=0&&nx
      
       =0&&ny