Problem A The Most Distant State

Input: standard input Output: standard output

Time limit: 13.333 seconds

解题思路：题目的意思是给你一个初始化的3*3 “数字拼图”，叫你找出需要移动步数最多的那个拼图的情形，而且输出移动的步骤，当然移动步数最多的比较是建立在不同的拼图情形上的。题目为特判，所以输出可能有所不同。解题思路用BFS放队列里扫描“数字拼图”中空白处的上下左右方向，将拼图中数换回位数为9位的大整数，所以共有9！个整数，有出现的将其放到set中，并不断更新移动步骤的长度和当前的拼图情形，判断set中元素的个数是否达到9！break出来输出更新后的目标拼图情形和移动步骤

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define SIZE 9  7 #define INF 362880  8 #define MAXN 1000000  9 using namespace std; 10  11 typedef int subType[SIZE]; 12 typedef struct type{ 13     subType value; 14     string step; 15 }type; 16  17 set
          
           visit; 18 queue
           
            puzzle; 19 20 int dir[][2] = { { 0, -1}, { 0, 1}, {-1, 0}, { 1, 0}}; 21 string dirFlag[] = { "L", "R", "U", "D"}; 22 int store_cnt; 23 int store_num; 24 string store_string; 25 bool try_to_insert(type from) 26 { 27 int sum = 0; 28 for(int i=0; i
            
             =0 && newx < 3 && newy >=0 && newy < 3) 65 { 66 type next; 67 memcpy(next.value , s, sizeof(subType)); 68 next.value[newz] = s[z]; 69 next.value[z] = s[newz]; 70 next.step.assign(cur.step); 71 next.step += dirFlag[d]; 72 if(try_to_insert(next)) 73 { 74 puzzle.push(next); 75 if(store_cnt == INF) 76 { 77 flag = 1; 78 break; 79 } 80 } 81 } 82 } 83 if(flag) break; 84 } 85 } 86 87 int main() 88 { 89 #ifndef ONLINE_JUDGE 90 freopen("input.txt", "r", stdin); 91 92 #endif 93 94 int T; 95 cin>>T; 96 97 for(int t=1; t<=T; ++t) 98 { 99 type input;100 for(int i=0; i
             
              >input.value[i];103 }104 input.step = "\0";105 while(!puzzle.empty()) puzzle.pop();106 puzzle.push(input);107 Traverse();108 cout<<"Puzzle #"<