huangdada156 2017-01-11 03:31 采纳率: 0%
浏览 1582

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 2017-01-11 09:16
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名