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

 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 }