1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import Queue;
st = [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]];
def find():
    queue = Queue.Queue();
    x = raw_input();
    x = x.split(' ');
    s='';
    for i in x:
        s+=i;
    queue.put(s);
    step = {};
    step[s] = 0;
    l = [];
    p = getpos(s);
    if meet(p):
        return 0;
    while not queue.empty():
        state = queue.get();
        for i in range(1,4):
            for m in range(1,9):
                nextstate = move(i,m,state);
                np = getpos(nextstate)
                if checkState(np) and not visited(nextstate,l):
                    step[nextstate] = step[state] + 1;
                    l.append(nextstate);
                    if meet(np):
                        return step[nextstate];
                    queue.put(nextstate);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX