题目描述：
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：用数组int b[] = {0,0,0,0,0,0,0,1,1,1,1,1}; 生成对应12个位置的全排列
dfs判断是否有5个1可以满足题目条件的连通方式
这里注意 设置已经访问的时刻 （这里是第一种）
（1）进去某个点即访问
（2）判断下一个位置可行后设置访问过
1AC代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
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 <<ans;
return 0;
}
2这个是错误答案：原本想通过dfs逐个判断累加个数除上5 但是 结果不对 也不知道为啥
#include<cstdio>
#include<cstring>
#include<iostream>
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<row&&ny>=0&&ny<col){
if(!vis[x][y]){
vis[x][y] = true;
dfs(nx,ny,step+1);
vis[x][y] = false;
}
}
}
}
int main()
{
memset(vis,false,sizeof(vis));
int cnt = 1;
for(int i = 0; i < row; ++i){
for(int j = 0; j < col; ++j){
map[i][j] = cnt++;
}
}
for(int i = 0; i < row; ++i){
for(int j = 0; j < col; ++j){
dfs(i,j,0);
}
}
cout << ans/5;
return 0;
}