首页 > 编程语言 > 详细

蓝桥杯2017-省赛-C/C++-A组2题

时间:2020-01-21 20:37:38      阅读:41      评论:0      收藏:0      [点我收藏+]

标签:iostream   emp   ret   idt   spa   com   

题目
标题:跳蚱蜢

如图 p1.png 所示:
有9只盘子,排成1个圆圈。
其中8只盘子内装着8只蚱蜢,有一个是空盘。
我们把这些蚱蜢顺时针编号为 1~8

每只蚱蜢都可以跳到相邻的空盘中,
也可以再用点力,越过一个相邻的蚱蜢跳到空盘中。

请你计算一下,如果要使得蚱蜢们的队形改为按照逆时针排列,
并且保持空盘的位置不变(也就是1-8换位,2-7换位,...),至少要经过多少次跳跃?

注意:要求提交的是一个整数,请不要填写任何多余内容或说明文字。

技术分享图片

思路

bfs

代码

 1 #include<iostream>
 2 #include<string.h>
 3 #include<queue>
 4 #include<stdlib.h>
 5 #include<cmath>
 6 #include<stdio.h>
 7 #include<algorithm>
 8 #define maxx 1000000000
 9 using namespace std;
10 long long int str_t_int(char str[]){//str to int
11      long long int sum=0,ll=1;
12      for(int i=8;i>=0;i--){
13          sum=sum+((str[i]-0)*ll); 
14          ll=ll*10;
15      }
16      return sum;
17 }
18 
19 int find_9(char str[]){
20      int loc_9;
21      for(int i=0;i<10;i++){
22          if(str[i]==9) loc_9=i;//找到空盘的下标 
23      }
24      return loc_9;
25 }
26 
27 void int_t_str(int num,char *str){
28      int i=8;
29      while(num%10){
30          *(str+i)=(char)(num%10+0);
31          num/=10;
32          i--;
33      }
34      return;
35 }
36 int dir[4]={-2,-1,1,2};//跳跃的方案 
37 bool index[maxx];//各种情况是否已经判断的标记
38   
39 int bfs(){
40      long long int start=123456789;
41      long long int end=876543219;
42      queue<int> q;
43      queue<int> qc;
44      q.push(start);
45      qc.push(1);    
46      char str[10];
47      long long int temp,loc_9,temp_char,cnt;
48      int find=0;
49      index[start]=1;
50      cnt=1;
51      while(1){
52          temp=q.front();//获取当前q队列的首部 
53          cnt=qc.front();//获取当前qc队列的首部
54           
55          int_t_str(temp,str);// int to str
56          
57          loc_9=find_9(str);//确认9的位置 
58          
59          for(int i=0;i<4;i++){//开始逐个试探 
60          
61              temp_char=str[loc_9];//模拟跳跃 
62              str[loc_9]=str[(loc_9+dir[i]+9)%9];
63              str[(loc_9+dir[i]+9)%9]=temp_char;
64              
65              
66              temp=str_t_int(str);//str to int
67             
68 
69         
70              if(!index[temp]){//是否重复 
71              
72                  if(temp==end){//找到队列 
73                      return cnt;
74                  }else{//标记temp,同时将temp压入队列中 
75                      index[temp]=1;
76                      q.push(temp);
77                      qc.push(cnt+1);
78                  }
79              }
80              
81              temp_char=str[loc_9];//回归原位,进行其他方向的试探 
82              str[loc_9]=str[(loc_9+dir[i]+9)%9];
83              str[(loc_9+dir[i]+9)%9]=temp_char;    
84          }
85          q.pop(); //q,qc队列弹出 
86          qc.pop();
87          
88      }
89      
90 }
91 int main(){
92      cout<<bfs()<<endl;
93 
94 }

蓝桥杯2017-省赛-C/C++-A组2题

标签:iostream   emp   ret   idt   spa   com   

原文:https://www.cnblogs.com/memocean/p/12222926.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号