2 huangdada156 huangdada156 于 2017.01.11 11:31 提问

C语言蓝桥杯16年第七题运行了一上午还是不知道哪里错了?

剪邮票

如【图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;

}


1个回答

shen_wei
shen_wei   Ds   Rxr 2017.01.11 17:16
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!