- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
题目描述】; W1 w4 N6 Y9 S
! Q: F# t j8 _2 A 在一个 3×3 的网格中,1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
1 S$ }, O0 V4 y+ q: h1 P" h( v
( _6 i9 x9 {$ D! G2 i例如:0 u/ |+ \$ q0 f. @/ H
/ o1 Y$ }( h" W$ S0 v1 2 3
; _) ? h8 Z! Y8 Z# R8 tx 4 61 g4 @5 ]: _/ Z- T5 u
7 5 8& A' o' J* A9 i p
在游戏过程中,可以把 x 与其上、下、左、右四个方向之一的数字交换(如果存在)。我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
! P' Z9 F6 y3 [* W7 p' ~
' R& a0 O( K/ X3 d6 N1 2 3
( _* \' d- u& V1 S4 5 64 f! Z# _- y8 ^# t- c
7 8 x
2 g5 b+ d& {8 { 例如,示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下% m4 Q9 O( i4 Y) ], ~7 E5 n# ]
/ i$ h3 h- Z8 X+ j$ r1 2 3 1 2 3 1 2 3 1 2 3( U) p4 U1 I* b5 ~( C
x 4 6 4 x 6 4 5 6 4 5 6
7 ?# v% L8 z7 i) \$ e- E7 5 8 7 5 8 7 x 8 7 8 x
( y0 T8 B( K3 A3 T 把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。
/ l& ~0 {, D7 q, i$ Q1 m h# o3 I! G1 G: y( \6 e6 u
【输入格式】6 s/ @7 i5 r. |3 }5 H- o) E7 T8 N. D! u
( i# M' \! n7 y/ q0 s$ m2 Q
输入占一行,将 3×3 的初始网格描绘出来。例如,如果初始网格如下所示:- q- f' M* O/ g8 D1 ]& X% Y
+ S5 u" r- l9 Y! v% s7 i
1 2 3 + X. V5 ]0 M* |4 H# X+ U
x 4 6 # v7 u# N4 K! l% F1 c
7 5 8
9 |& V& B$ z* X; h" L 则输入为:1 2 3 x 4 6 7 5 8
, w( V S3 Y+ ~8 {& n3 r+ K$ l/ t& }0 \. D
【输出格式】
8 w; G7 I! i6 h0 P% u3 J0 i5 b. y* q& G. X
输出占一行,包含一个整数,表示最少交换次数。
$ m" J+ t& x- K% J; T% V H$ K$ Q* y2 y$ k5 }/ ]
如果不存在解决方案,则输出 −1。
+ f6 d/ ?6 e& m; m( X8 Z1 w# X7 C% k1 n* F( f3 p- G1 V
【输入样例】! i% `# i& a8 R. k
6 ]' l# M0 K3 C' A
2 3 4 1 5 x 7 6 8
; V/ e$ |8 Z; ^【输出样例】7 W7 l3 T% q7 T' I6 E
$ l" c- \) X! [# P' H2 U6 e% @" c
19$ g7 C( S/ J: r; Q7 a/ {
【解题思路】) k/ x2 R f2 t
' h5 Z1 x9 ]9 e
简答题,用BFS遍历查找即可。
5 `; r+ \/ b: y% x) C5 R6 N" h& T2 K( h4 r" ~/ c
【Python程序代码】2 Y# G4 Z; X4 a
. V) _6 {, n- ?9 K
from collections import *
0 M) @ J1 C9 C5 \' p3 L, Ipd = ['0','1','2','3','4','5','6','7','8','x']
. Q9 j2 I$ N0 ]; b) N! ~/ y; Nnorm = "".join(pd)
* A+ }3 N( z7 r( xdir = [1,-1,3,-3]
* Z5 h; a1 N( m6 o1 J- r) hs = ['0'] + list(map(str,input().split()))" w2 m4 n3 L. e* B f6 l u* X/ b
idx = s.index('x')' g, O0 c+ L! W9 }9 L1 Z
mp = defaultdict(int)
% M; u2 h b8 N h/ [def bfs():* u8 C- ?' n) P, F2 ~- H6 l
q = deque()9 R# ^, t9 B+ @5 l/ K' ?% Q
step = 0
+ K: \7 b/ I2 ]2 {6 R3 j* _1 d! o' f q.append( [s,idx,step] ): L7 ^0 H1 r& [# d3 }6 G, n, ^: G
ns = "".join(s)
5 g% z5 X' `& f) R" x: N mp[ns]=1: @: u n4 _$ p% ]6 t- c
flag,res = 0,-15 R7 Y% ], a+ w" E7 T7 e6 o7 ?# E2 o& z
while q:
) N/ W, V. x" h; t/ o- X4 U ss,sidx,step = q.popleft()! k9 ~# [! m0 j" x
if "".join(ss)==norm:- d: E9 `* v: l7 ^; s6 K
res = step" U+ _8 x0 }7 |2 r
break5 x: s7 h3 u9 }3 L
for i in dir:$ y/ a& g( [* w" _: G A1 L
teps = ss.copy()
' o {" a# S9 x+ u3 ~ nidx = sidx + i
$ O) e; n' S2 h/ C2 u% W5 G if nidx<1 or nidx>9:continue8 T1 i+ m( o0 K
if (sidx==3 or sidx==6) and i==1:continue0 t a/ a* f) W
if (sidx==4 or sidx==7) and i==-1:continue/ K4 @- q8 E$ r+ Z ~
teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
; X1 @( y8 p8 z/ W2 P ]7 p6 v nteps = "".join(teps) K8 j- c) w- v$ w: N* |1 W
if mp[nteps]:continue3 L9 u2 T; U# X* G \8 ~4 G( f
mp[nteps]=1) c4 x5 b" _% Z0 M7 |: ^
q.append( [teps,nidx,step+1] )
- W) c7 o! [: j- N8 E8 ~ print(res)
* \% c3 `# U \: [' r @( `# Tbfs()2 S" `/ a6 P& W5 m2 E
7 C0 @3 t; H9 q8 n2 G0 ^/ Z; m9 U' H# I( L) r( e
( n2 r# P4 |% \2 Q% a& P0 n) s; a9 p* |. q3 l
# w7 W% ]4 g* ~, P9 ?% S |
-
-
代码.txt
2.23 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价: 2 点体力 [记录]
[购买]
zan
|