Uva 10085 The most distant state

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<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<queue>
  5 #include<set>
  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<int>visit;
 18 queue<type>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<SIZE; ++i) sum = sum*10 + from.value[i];
 29     if(visit.count(sum) == 0)
 30     {
 31         visit.insert(sum);
 32         if(store_string.length() <= from.step.length())
 33         {
 34             store_num = sum;
 35             store_string.assign(from.step);
 36         }
 37         store_cnt++;
 38         return true;
 39     }
 40     return false;
 41 }
 42 
 43 void Traverse()
 44 {
 45     visit.clear();
 46     store_cnt = 0;
 47     store_string = "\0";
 48     store_num = 0;
 49     try_to_insert(puzzle.front());
 50     while(!puzzle.empty())
 51     {    
 52         type cur = puzzle.front();
 53         puzzle.pop();
 54         subType& s = cur.value;
 55         int z=0;
 56         for(; z<SIZE && s[z] != 0; ++z);
 57         int x=z/3, y = z%3;
 58         int flag = 0;
 59         for(int d=0; d<4; ++d)
 60         {
 61             int newx = x + dir[d][0];
 62             int newy = y + dir[d][1];
 63             int newz = newx * 3 + newy;
 64             if(newx>=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<SIZE; ++i)
101         {
102             cin>>input.value[i];
103         }
104         input.step = "\0";
105         while(!puzzle.empty()) puzzle.pop();
106         puzzle.push(input);
107         Traverse();
108         cout<<"Puzzle #"<<t;
109         for(int i=0, into=100000000; i<SIZE; ++i, into /= 10)
110         {
111             int temp = store_num/into;
112             if(i%3 == 0) cout<<endl;
113             else cout<<" ";
114             cout<<temp;
115             store_num %= into;
116         }
117         cout<<"\n"<<store_string<<endl;
118         cout<<endl;
119     }
120     return 0;
121 }