python 解决八数码问题

2744557306

题目描述】
2 E! d/ {3 q- e7 z
3 V2 H1 c2 X) m( r  Y        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

  X7 {+ J! C. K1 B3 @7 z' }例如：

1 2 3
, Y7 Q- V$ K  M8 B, C" rx 4 6
: G. l1 ]# Y$ N( {8 R6 q7 5 8
6 i4 \2 G+ n; N' k6 y. l        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

# b5 j! |) R8 l# z# j; I1 2 3
4 5 6
7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

4 n7 S! N  d3 d, [- X) |1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x
% M0 x3 r; q6 Q         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

3 k3 h1 }3 N4 z. _【输入格式】
9 e. B  X. i- J9 F/ `
; u  s. f9 h0 j6 `        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
: o5 Y4 H7 S: ]# }, y5 H& A' D
" }4 c3 u! E6 S' u2 K1 2 3
x 4 6
2 y3 U4 ~. }+ J2 V7 5 8
4 T3 a/ e5 h- k# U/ \" P4 ]- \% p- f        则输入为：1 2 3 x 4 6 7 5 8

# E7 e, T4 i) h【输出格式】

        输出占一行，包含一个整数，表示最少交换次数。
# |1 p6 E4 T, |8 W, s1 Q
! _2 R# \$ A. Z5 b% b        如果不存在解决方案，则输出 −1。
& C1 ~# \% |3 G
【输入样例】
2 `' x  @: p1 c1 S
2 3 4 1 5 x 7 6 8
【输出样例】

19
【解题思路】
6 q: R! s9 Q: C! c/ v
) F/ E- Q. k, K" W        简答题，用BFS遍历查找即可。

【Python程序代码】
* F  h$ ?5 y4 `( y! V3 {
, W; S6 [* ?3 Y) T6 W% R7 z5 ^from collections import *
) j! q. Y5 f0 e- Rpd = ['0','1','2','3','4','5','6','7','8','x']
# C+ f) m' m7 G" onorm = "".join(pd)
% U! N- t" Z: `# v" q# v) T8 A& kdir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
7 S$ ~( M: J! O- r1 ?! pidx = s.index('x')
- i% j2 e) L5 _  Wmp = defaultdict(int)
def bfs():
- t8 [  _/ u9 W9 U4 |    q = deque()
) p0 E! p% F  P5 v1 I    step = 0
" |  y; g1 R2 x* r    q.append( [s,idx,step] )
3 M& Z: b; E) \( C' N# ?6 |    ns = "".join(s)
3 l2 V# c( t/ J* o7 e( G2 Y8 ^    mp[ns]=1
    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
) m% {- T! L! g& |        if "".join(ss)==norm:
            res = step
$ F) z  l% q, }& p            break
2 v" w! @9 P8 t  C        for i in dir:
3 ^% b, V' W% \$ j$ W. T            teps = ss.copy()
            nidx = sidx + i
' P1 h8 x& G4 d; }            if nidx<1 or nidx>9:continue
, _0 j; U$ I1 z- b( y, ?; g4 }            if (sidx==3 or sidx==6) and i==1:continue
            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
! F8 d% Z4 [. d( e            if  mp[nteps]:continue
% M2 j( u! o" M' ]: w2 G            mp[nteps]=1
8 N% Q( P$ J- O$ [- ?9 l! X            q.append( [teps,nidx,step+1] )
' H8 [+ D( [7 u% A1 A    print(res)
bfs()

/ ]& O7 u: K0 U1 g+ M9 L  k
0 p' Q( I+ l1 Y3 ~# d( z
' [: O* s) j/ ^6 ]$ C& i4 _
. ?* O7 R  [& r2 c# j# z, K