python 解决八数码问题

2744557306

题目描述】
3 T! P% Z, T4 ^6 _) l4 t
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：

7 w; k, x  S+ L' j( d. M1 2 3
x 4 6
7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
+ ?3 m% {, j" U' J2 I0 S4 5 6
7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
* P. a6 w1 y- s: c4 H7 J
. n9 _! s8 h) T5 Q1 2 3   1 2 3   1 2 3   1 2 3
* T, h5 @! U: a5 Y% D0 nx 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

6 U4 A2 L" f5 S2 Z% A, X1 C# s【输入格式】
6 G5 c& }( B5 o! Y2 u0 I* S$ [3 r
/ `' t% }5 O( F6 [6 K        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8
, r( @6 h/ c7 O% Y        则输入为：1 2 3 x 4 6 7 5 8

4 ~2 @! x5 q' T8 x【输出格式】
0 Q% S: }: E4 R% z0 u
1 r5 M/ j/ I) j3 z8 l/ E( `' ]0 ]        输出占一行，包含一个整数，表示最少交换次数。
7 u4 C, T7 z, S' D8 G
        如果不存在解决方案，则输出 −1。
% n. V! b' r$ V8 I6 P) f
3 s& e: m8 [' P【输入样例】
% b- r* l* K2 i9 P9 k( ^2 Z: ^
2 3 4 1 5 x 7 6 8
【输出样例】
) Q" T; S6 q) r2 Q  ?6 Z$ c
19
+ q6 J3 T' c+ V+ B0 v6 C【解题思路】
4 R8 c' A$ d  ~" }% X$ \) ~3 l+ u
        简答题，用BFS遍历查找即可。

【Python程序代码】
1 [) B7 ~/ P& `- M- B& C
from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
$ j2 {0 j0 P( Knorm = "".join(pd)
" a7 ?% v; U0 {5 z! f$ L, ldir = [1,-1,3,-3]
# A5 N. ]/ P( L  fs = ['0'] + list(map(str,input().split()))
idx = s.index('x')
' w4 w6 X( E) s7 c& S. ?mp = defaultdict(int)
; g9 f$ o2 }$ V2 `! U3 Z) Q: kdef bfs():
" o+ r; v; A$ H( P2 Z    q = deque()
8 L1 u" p; Q5 u1 z3 N; s! [    step = 0
    q.append( [s,idx,step] )
2 _7 l6 u, s4 O+ U8 M    ns = "".join(s)
    mp[ns]=1
% N- D! n& f& f! @: K    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
* u1 q0 Z( [% Z+ a. P# p5 [* O/ i            res = step
# }2 D3 F% H0 n& N- J            break
+ T& }& G! F3 j# V        for i in dir:
            teps = ss.copy()
            nidx = sidx + i
; s. c0 b  b% b  p; Z            if nidx<1 or nidx>9:continue
1 b7 x! ]& l5 f/ [3 T8 P            if (sidx==3 or sidx==6) and i==1:continue
8 [, j$ _) F! O+ _% }            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
$ Y" O) b' z! c( H# t$ b5 M            nteps = "".join(teps)
            if  mp[nteps]:continue
            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
. n( }9 S. [" C, @5 o    print(res)
bfs()



$ l4 Z, W  f1 O4 n: L0 t
4 v4 ~/ l! x3 k7 g3 }6 O