python 解决八数码问题

2744557306

题目描述】
" m8 p& N" w% M; g, U
5 u# E9 T6 n- @0 u; q        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
) K6 ~6 \! U  e, L. {8 y( F, ^9 R
例如：
7 o0 F5 x! F, a
# R8 |6 S' _) j" m' Q1 2 3
8 N# ~) z5 m+ C, zx 4 6
* Z% E! {* i) t7 5 8
' Z3 j1 |/ h' B1 H! |        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
% s! l4 \1 C0 V) T5 R$ C
1 2 3
4 5 6
7 8 x
% `' a. a9 v+ `( V        例如，示例中图形就可以通过让 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
- o8 L4 z% R" |2 K$ q  d1 x" r& A7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
, _/ u9 U3 N! f( D9 i8 F- H; [
% W7 S% s2 B) u. B, e# V【输入格式】
/ C% z. b8 g- j% x) S! z  j
" R% {; x8 U2 c5 \- @! Z        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
- Z% E  n  c' H' q( Q0 y* W
1 2 3
x 4 6
7 5 8
8 k8 j3 K/ G! Z5 T) X  P0 P        则输入为：1 2 3 x 4 6 7 5 8

+ F8 L; G4 B2 q; b1 L! v: i' P【输出格式】
& v9 m% q. y4 V" ~
        输出占一行，包含一个整数，表示最少交换次数。

7 Y9 d3 a# p, ]7 y& n6 Y. N/ N" b        如果不存在解决方案，则输出 −1。

5 h6 `& d" M2 r( N【输入样例】

2 3 4 1 5 x 7 6 8
4 E8 q' Z' e) h2 T0 y( I+ j% e【输出样例】
. x) }( T7 f! t4 w
19
【解题思路】

        简答题，用BFS遍历查找即可。
9 p7 Y+ A. ]8 x  G# Y
) y$ s% m* S9 u9 E; p【Python程序代码】

from collections import *
# g- p, L+ d+ F" l/ c) [pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
5 U% F* ]) n) ?) O8 o" Ydir = [1,-1,3,-3]
3 I$ r) I! u8 rs = ['0'] + list(map(str,input().split()))
; l& F! v; d' {+ B$ zidx = s.index('x')
" [  U; z" R2 W  T* Imp = defaultdict(int)
- D/ |4 ^: h( b  G! ndef bfs():
: u) i  V2 l9 d4 A    q = deque()
    step = 0
    q.append( [s,idx,step] )
    ns = "".join(s)
( u0 b/ Y# D1 l' t    mp[ns]=1
    flag,res = 0,-1
( T$ g+ S& t, _+ c' `1 P    while q:
        ss,sidx,step = q.popleft()
5 p9 t" @& t7 t        if "".join(ss)==norm:
: Y8 J. p" M6 y7 v; c/ c: I* A$ A; I            res = step
1 @1 n3 Y, ^3 B% @            break
  q5 o, i5 Y1 `9 D) e" l& a6 E        for i in dir:
- I! |2 s9 r* |6 w            teps = ss.copy()
            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
            if (sidx==4 or sidx==7) and i==-1:continue
1 X9 F% f+ j3 J2 |. M5 _+ q" n            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
            if  mp[nteps]:continue
# d/ T( j/ Z- e2 P8 W& v            mp[nteps]=1
0 v$ ?# r0 Y8 B7 {& V            q.append( [teps,nidx,step+1] )
    print(res)
9 H# A2 r* k# M& M, i; F. Fbfs()
3 }. G6 H- Q; M, p% ^' w+ x