Admiral（雙向BFS + Hash）

Problem Description

Suppose that you are an admiral of a famous naval troop. Our naval forces have got 21 battleships. There are 6 types of battleships. First, we have got one flagship in which the admiral must be and it is denoted by number 0. Others are denoted by number from 1 to 5, each of them has 2, 3, 4, 5, 6 ships of its kind. So, we have got 21 battleships in total and we must take a giant battle against the enemy. Hence, the correct strategy of how to arrange each type of battleships is very important to us. The shape of the battlefield is like the picture that is shown below. To simplify the problem, we consider all battleships have the same rectangular shape.

Fortunately, we have already known the optimal state of battleships. As you can see, the battlefield consists of 6 rows. And we have 6 types of battleship, so the optimal state is that all the battleships denoted by number i are located at the i-th row. Hence, each type of battleship corresponds to different color. You are given the initial state of battlefield as input. You can change the state of battlefield by changing the position of flagship with adjacent battleship. Two battleships are considered adjacent if and only if they are not in the same row and share parts of their edges. For example, if we denote the cell which is at i-th row and j-th position from the left as (i,j), then the cell (2,1) is adjacent to the cells (1,0), (1,1), (3,1), (3,2). Your task is to change the position of the battleships minimum times so as to reach the optimal state. Note: All the coordinates are 0-base indexed.

Input

The first line of input contains an integer T (1 <= T <= 10), the number of test cases.  Each test case consists of 6 lines. The i-th line of each test case contains i integers, denoting the type of battleships at i-th row of battlefield, from left to right.

Output

For each test case, if you can’t reach the goal in no more than 20 moves, you must output “too difficult” in one line. Otherwise, you must output the answer in one line.

SampleInput

1
1
2 0
2 1 2
3 3 3 3
4 4 4 4 4
5 5 5 5 5 5      

SampleOutput

3

題意就是給你一個6*6的塔，上下兩個相鄰的機關可以進行交換，問最少進行幾次交換，可以得到
0
1 1
2 2 2
3 3 3 3
……………………
這種狀态，開始思路是用A*做，結果A*不是很熟練，沒搞出來，寫了個直接搜尋炸了，然後我也是看了一下網上部落格，使用雙向搜尋就行了。
思路就是從末尾開始往前搜尋10步，從開始狀态往後搜尋10步，分别狀态壓縮一下存在map中，然後就看有沒有兩種相同的狀态，否則就輸出太難了。
代碼：
      

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int fx[4][2] = {1,0,1,1,-1,-1,-1,0};    //左下，右下，左上，右上
 5 
 6 struct node{
 7     ll p[6][6];
 8     int r,c;
 9     int flag;
10     int step;
11 
12     node(){}
13     node(int _r,int _c,int _flag,int _step):r(_r),c(_c),flag(_flag),step(_step){}
14 };
15 
16 queue<node>q;
17 map<ll,ll>p[2];　　//分别存儲兩個方向的bfs狀态
18 
19 ll _hash(node a){　　//用hash壓縮路徑狀态
20     ll res = 0;
21     for(int i = 0; i < 6; i++){
22         for(int j = 0; j <= i; j++){
23             res = res*6 + a.p[i][j];
24         }
25     }
26     return res;
27 }
28 
29 int bfs(node &s,node &e){
30     while(!q.empty()){
31         q.pop();
32     }
33     p[0].clear();
34     p[1].clear();
35     q.push(s);
36     q.push(e);
37     p[s.flag][_hash(s)] = 0;　　//必須要标記一下，因為後面會用到count函數查詢是否存在
38     p[e.flag][_hash(e)] = 0;
39     while(!q.empty()){
40         node now = q.front();
41         q.pop();
42         ll sta = _hash(now);
43         if(p[!now.flag].count(sta)){
44             int num = p[!now.flag][sta] +  now.step;
45             if(num <= 20)
46                 return num;
47             else
48                 continue;
49         }
50 
51         if(now.step >= 10)　　//處理10步即可
52             continue;
53         for(int i = 0; i < 4; i++){
54             node nxt = now;
55             nxt.step++;
56             nxt.r += fx[i][0];
57             nxt.c += fx[i][1];
58             if(nxt.r < 0 || nxt.r > 6 || nxt.c < 0 || nxt.c > nxt.r)
59                 continue;
60             swap(nxt.p[now.r][now.c],nxt.p[nxt.r][nxt.c]);
61             if(p[nxt.flag].count(_hash(nxt)) == 0)
62                 p[nxt.flag][_hash(nxt)] = nxt.step;
63             q.push(nxt);
64         }
65     }
66     return -1;
67 }
68 
69 int main(){
70     int t;
71     cin>>t;
72     node s, e;
73     while(t--){
74         for(int i = 0; i < 6; i++){
75             for(int j = 0; j <= i; j++){
76                 cin>>s.p[i][j];
77                 if(s.p[i][j] == 0)
78                     s.r = i, s.c = j;
79                 e.p[i][j] = i;
80             }
81         }
82         s.flag = 0;
83         s.step = 0;
84         e = node(0,0,1,0);
85         int ans = bfs(s,e);
86         if(ans >= 0 && ans <= 20)
87             cout << ans << endl;
88         else
89             cout << "too difficult" << endl;
90     }
91     return 0;
92 }