- 在线时间
- 480 小时
- 最后登录
- 2026-6-1
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7823 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2934
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1174
- 主题
- 1189
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
题目描述】7 _& g2 h/ P) J* F7 U
. x2 N: L5 J1 }% Y
在一个 3×3 的网格中,1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。2 C! r! ]; B2 h% w3 d9 y
# C2 D/ M( d! z% R) Q, M例如:2 b) W4 d* y$ A0 b: `5 `9 l
6 C; V' w P1 \* ^% K7 M! I% P1 2 3+ u# u( V3 D+ G
x 4 6
% p' U$ m5 P( V4 x3 k7 Y" z9 s7 5 8( p$ C/ d# V- p; ?9 u; ~, ?
在游戏过程中,可以把 x 与其上、下、左、右四个方向之一的数字交换(如果存在)。我们的目的是通过交换,使得网格变为如下排列(称为正确排列):6 y" U' G7 N0 ]8 r" q6 c) q5 E; f
: t4 f- X! V' L' C3 w. F
1 2 34 s; f2 c: O9 O% M4 z' H
4 5 6
5 Z# ]$ x: B' a/ W* Q0 W7 8 x+ ?, \/ Y+ S5 p8 |; P
例如,示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下% N# {2 j( X' N' G
; L* J4 r2 w2 w' E* i
1 2 3 1 2 3 1 2 3 1 2 3+ Z' T1 Y* ~- h9 m' B; h) j
x 4 6 4 x 6 4 5 6 4 5 6( O) i# r9 [+ u
7 5 8 7 5 8 7 x 8 7 8 x
0 ^) o" ]0 C& i7 C. v 把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。7 a. Q* F2 L2 C, l% W9 h
) `/ ^ ?* F! |6 C1 P1 p6 P
【输入格式】
, p- O. F6 w2 @; E5 X7 r! z7 m7 N4 j
输入占一行,将 3×3 的初始网格描绘出来。例如,如果初始网格如下所示:
; d' r3 r# l* s; A( S
% p: s/ }% a, J, M1 2 3
, F u+ H3 s1 }3 U% i4 P3 gx 4 6
# k+ w9 V* R) z- \7 w- L7 5 8
! b; P6 e' z6 i* }8 Q% Z 则输入为:1 2 3 x 4 6 7 5 8
% `, ]0 A; ?# i% F' ~% @- O
% P. ` S+ z( x# M+ s7 `" ^' `【输出格式】1 B4 ?3 r7 d) _" E9 k
- ]( V$ {7 I# R9 p F7 L% e3 ^
输出占一行,包含一个整数,表示最少交换次数。
' N6 O) h) D9 d# ?( i* r& K9 A3 t. @% k% ^& Q2 |- N( W3 B8 E
如果不存在解决方案,则输出 −1。% B; Q0 F2 F3 B, I, F& F
/ e) Y& C0 [- ^! R7 [( o; P4 v+ n
【输入样例】
2 {7 w! f1 m( {4 T4 j" _ l3 j1 r: l# j1 v) _% X# i
2 3 4 1 5 x 7 6 8
) \0 K) Y1 N8 U& @【输出样例】
. U( U: t$ P$ n, c7 c. z1 L7 o( h9 E! E5 b1 A- | m, a
19
0 |' A1 R/ S0 K) ]1 K* q【解题思路】8 _8 o9 w3 ^1 Q! t- {! ^2 N
" b; W3 B" S8 B& F
简答题,用BFS遍历查找即可。+ e+ c4 K( X# G2 R+ T
9 O0 c% N: S6 y, [% _【Python程序代码】, a7 v1 g0 f. x, R3 }* X+ U
/ o2 T, @! \, q) C6 w: Nfrom collections import *
$ X6 }& g; c: H2 U3 D. jpd = ['0','1','2','3','4','5','6','7','8','x']+ {7 t! D6 ]8 u4 `( B$ p- a) g* c, {) d _
norm = "".join(pd): H) r% K; }! {
dir = [1,-1,3,-3]; p* d0 o* [; D( ^2 r# y( h
s = ['0'] + list(map(str,input().split()))
9 e9 ~' E* @) h: }idx = s.index('x')% C- I1 ^8 C4 G: E* a5 L
mp = defaultdict(int)
% m; v1 }5 I6 ?# J, v% V# P9 V3 `$ kdef bfs():8 M" Y) ~* A! t _
q = deque()- u* l; c8 f* f( o! c' e
step = 0
0 N9 u2 l5 u) s3 \$ ^; ^$ | q.append( [s,idx,step] )( m/ ? X1 L/ [0 R. {8 a
ns = "".join(s)
$ |9 X* O0 [1 Y7 K mp[ns]=1
! t( ]# u5 {% Q2 ~ `6 e9 ] flag,res = 0,-1. J( u4 G- a* `6 s5 d
while q:
2 G& _+ ]/ M9 C( ], P# ^ ss,sidx,step = q.popleft()
8 A5 f( |" ]' g" S+ ~* a3 ? if "".join(ss)==norm:5 _- P" N9 I; T0 ~1 t
res = step
: E, A% D7 ]8 x( u; ^+ Q) y5 @- u break
/ T5 a" F9 X: K/ x- O for i in dir:, ]! n* b3 k; m; |6 t" }1 K
teps = ss.copy()
* Y+ J* e. b4 f* \ nidx = sidx + i! H2 |5 k/ C+ N4 J& Q# c0 E
if nidx<1 or nidx>9:continue4 j" K. K/ x. O5 U" T
if (sidx==3 or sidx==6) and i==1:continue
- \& g' b' ~2 t if (sidx==4 or sidx==7) and i==-1:continue7 Q" {: f3 D- T4 ^. V% w( ~% Z
teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
- `7 k+ a) M8 Z9 v2 I( _( B# n nteps = "".join(teps)
+ `, ]4 G8 V! J' F. m if mp[nteps]:continue
# q" g! N1 E: e' k mp[nteps]=1
/ B" f3 ~" x9 l* E" H# L q.append( [teps,nidx,step+1] )
( o: F+ c0 J/ E8 y; x print(res)6 c& |2 {& [- ~2 m4 A" P
bfs()9 N1 P# \' v2 g, P: n& Y1 p
y( L' g/ K, I8 G/ c0 F: N. i
$ O# X/ e/ `5 j/ N
% t# V! B# _- ?9 n
' V5 ~; W+ s( c% U6 a7 C [
& Z* z$ A# `( q. K& \+ ~$ l |
-
-
代码.txt
2.23 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价: 2 点体力 [记录]
[购买]
zan
|