剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
想法是用dfs搜索,执行五次然后出来,对每个点都执行一次,然后把执行的顺序放在数组里面,再剔除掉重复的,答案和网上的一直不一样不知道哪里错了~
#include
#include
using namespace std;
int a[3][4];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int fivenumber[5];
bool used[3][4];
int save[220][5];
int sum=0;
int count_save=0;
int coun=0;
bool judge(int m1[5],int m2[5]) //判断两个数组是否相同,相同则返回true
{
int mm=0;
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
if(m1[i]==m2[j]) mm=mm+1;
}
}
if(mm==5) return true;
else return false;
}
void saveit(int number[5]) //如果number里面没有已经储存过的数,那将它存进去
{
int flag=0;
for(int i=0;i<count_save;i++)
{
if(judge(save[i],number)==true){
flag=1;
break;
} //judge()返回true时表示这个数已经储存过了
}
if(flag==0){
for(int i=0;i<5;i++) save[count_save][i]=number[i];count_save++;
}
}
void dfs(int x,int y) //深度优先搜索邮票
{
coun=coun+1;
fivenumber[coun-1]=a[x][y];
used[x][y]=true;
if(coun==5){sum=sum+1;
cout<<fivenumber[0]<<" "<<fivenumber[1]<<" "<<fivenumber[2]<<" "<<fivenumber[3]<<" "<<fivenumber[4]<<endl<<endl;
saveit(fivenumber);
}
else{
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dir[i][0];
ny=y+dir[i][1];
if(nx<3&&ny<4&&!used[nx][ny]&&nx>=0&&ny>=0)
{
dfs(nx,ny);
used[nx][ny]=false;
coun--;
}
}
used[x][y]=false;
return;
}
}
int main()
{
for(int i=0;i<3;i++)
for(int j=0;j<4;j++){
a[i][j]=i*4+j;
used[i][j]=false;
}
for(int i=0;i<3;i++)
for(int j=0;j<4;j++){
dfs(i,j);
coun=0;
}
for(int i=0;i<count_save;i++) cout<<save[i][0]<<" "<<save[i][1]<<" "<<save[i][2]<<" "<<save[i][3]<<" "<<save[i][4]<<endl;
cout<<"count_save="<<count_save<<endl;
cout<<"sum="<<sum<<endl;
return 0;
}