2030ssxx level
获赞
1
粉丝
0
关注
5
看过 TA
8
南京林业大学
2025
算法工程师
IP属地:江苏
暂未填写个人简介
私信
关注
//DFS好像不能是void函数//没什么好说的,上代码#include<algorithm>#include<iostream>#include<cstring>using namespace std;int totallen;int m;//棒子个数int stick[21];bool visit[21];bool cmp(int a,int b){return a>b;}bool DFS(int sum,int number,int position){if(number==3){//cout<<"yes"<<endl;return true;}// int sample=0;//不可能的重复边for(int i=position;i<=m;i++){int nsum=sum+stick[i];// if(nsum>totallen/4||visit[i]||sample==stick[i])continue;if(nsum>totallen/4||visit[i])continue;visit[i]=true;if(nsum==totallen/4)//凑成一条边{if(DFS(0,number+1,1))//下一条边从第一根棒开始测试return true;//else//{//    sample=stick[i];//说明这根棒子不能在这种情况下被用//}}else{if(DFS(nsum,number,i+1))return true;//else//{//    sample=stick[i];//}}visit[i]=false;}return false;}int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>m;totallen=0;for(int j=1;j<=m;j++){cin>>stick[j];totallen+=stick[j];}memset(visit,false,sizeof(visit));sort(stick+1,stick+1+m,cmp);if(totallen%4!=0||stick[1]>totallen/4){cout<<"no"<<endl;}else{if(DFS(0,0,1))//当前边的长度,拼好的边长数量,拼到第几个棒子cout<<"yes"<<endl;elsecout<<"no"<<endl;}}}
0 点赞 评论 收藏
分享
//DFS不难,想想也就能想明白了。但是要注意很多细节:每次都只是对当前情况做出改变,x\y坐标要重新定义新的#include<iostream>#include<cstring>using namespace std;int p;//行数int q;//列数bool visit[27][27];//int direction[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};int direction[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//先数字方向,后字母方向bool DFS(int i,int j,int step,string str)//i\j先行后列{if(step==q*p){cout<<str<<endl<<endl;return true;}else{for(int ii=0;ii<8;ii++){int ni=i+direction[ii][0];//i+=direction[ii][0];不能写成这样。因为该方法只对当前情况进行改变,直接修改i、j会对所有情况造成影响int nj=j+direction[ii][1];//j+=direction[ii][1];char col='A'+nj-1;//char row='1'+ni-1;//if(ni<1||ni>p||nj<1||nj>q||visit[ni][nj]==true)continue; //ninjvisit[ni][nj]=true;//仅仅是当前情况要修改 ninjif(DFS(ni,nj,step+1,str+col+row))//ninj{return true;}visit[ni][nj]=false;//算过之后就到下一种情况了,还要改回来   ninj}}return false;}int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>p>>q;memset(visit,false,sizeof(visit));cout<<"Scenario #"<<i<<":"<<endl;visit[1][1]=true;if(DFS(1,1,1,"A1")==false)cout<<"impossible"<<endl<<endl;}}
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务