python 解决八数码问题

2744557306

题目描述】
0 X1 N; ~- w. |4 G0 u8 p5 f! R' f
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：

) B/ y8 B" e1 w7 K" B9 d1 2 3
x 4 6
( S; W  T+ h3 j7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
! U2 p; U3 S! j6 `% O3 m
- Z! j' }9 o6 m0 T- e8 n$ _$ W1 2 3
# t' u6 B8 X; ^; g; b" t4 5 6
/ e, R1 B5 I: ]  R) Y2 t" D3 d7 8 x
! n& i6 T" w8 x' q( h  L1 [5 b        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

; U( W. N& D: Z/ i: V( A& t, u. V1 2 3   1 2 3   1 2 3   1 2 3
; J& v; K& U% P, K3 A" I6 kx 4 6   4 x 6   4 5 6   4 5 6
' H5 H& Y  x% l; B; e; e# D. n$ p7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

! }1 g& l/ s( n1 w【输入格式】
* n- Z" G6 ?6 q" U# a( B
" j& R+ u- J7 {+ b+ @$ f, D        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3
- R1 G9 ]6 [: }4 L7 b3 [0 r2 _x 4 6
% M9 h! H5 L# ^( o3 P: c2 |7 \7 X7 5 8
5 d/ R5 H% Z# P) ]0 r        则输入为：1 2 3 x 4 6 7 5 8
. k. G1 h  x  m# T7 ^" n: V
: x$ }/ O4 |+ @5 n9 U【输出格式】

        输出占一行，包含一个整数，表示最少交换次数。

) n8 I% T  q1 r        如果不存在解决方案，则输出 −1。
/ R; C& B9 m# e2 b5 ~: s
【输入样例】

2 3 4 1 5 x 7 6 8
【输出样例】

  g3 O( V% B; e+ |7 B3 t4 W19
* y  a2 H' f; R【解题思路】
6 R7 h" D  i# ^7 I2 w9 X
        简答题，用BFS遍历查找即可。

【Python程序代码】
! g( v' ~- e0 R7 z0 F
8 C9 s+ C7 {: {9 g! i- \0 [6 p5 |from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
# h4 ~" T' N0 H, knorm = "".join(pd)
- c% H5 @) q& edir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
- F' X+ J+ u* D/ W( o# C% W- _idx = s.index('x')
  i: T2 ?5 k, i8 D% v4 Gmp = defaultdict(int)
0 i5 p/ ^. x" j8 c/ h1 I5 Mdef bfs():
0 j3 t) C- v1 f$ i    q = deque()
    step = 0
    q.append( [s,idx,step] )
    ns = "".join(s)
8 G% |1 W' M; j* l3 @/ \- Q9 p    mp[ns]=1
    flag,res = 0,-1
    while q:
  m; n7 w( P& T' a        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
. H0 u9 A4 H9 A+ r0 m! S3 d            res = step
            break
        for i in dir:
            teps = ss.copy()
' M$ F3 z% C, S: h            nidx = sidx + i
            if nidx<1 or nidx>9:continue
! S) Q+ K7 i/ V$ q6 z4 m            if (sidx==3 or sidx==6) and i==1:continue
            if (sidx==4 or sidx==7) and i==-1:continue
7 e/ O/ k4 P* d9 `& W- ]            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
+ k* B$ d" i  o/ k6 [# p            if  mp[nteps]:continue
            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
' E, Q* w4 I' B0 U+ x    print(res)
: `6 ?# ^7 y: ^# D* }' ~bfs()
9 {' e( _$ r; E  L# D3 d

9 S$ w1 ~/ m! W; c$ U: G

' r0 J# {) N, b3 [2 t" I1 h