- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
题目描述】' Y& j. s, ] t+ C' T9 c( J# C
3 V) w2 v- o E% M 给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 (n,m)处,至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。
# w. w/ j3 {( S( W
) [! u2 N& A5 j8 E4 h6 O1 N【输入格式】: @9 g/ K& ^5 ]. R9 \8 n8 U* s
0 i* Q3 b6 n1 K/ I
第一行包含两个整数 n 和 m。
# D! }- v q8 x* Y# h9 B5 _6 D2 @6 ?4 ]$ }
接下来 n行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
- F' A* J: l6 y
5 S. M( D, K6 r9 ^( ^【输出格式】1 }" B& s/ B O H$ F9 L
4 g y+ k# Q) \3 K3 h 输出一个整数,表示从左上角移动至右下角的最少移动次数。
, e1 C% {, C8 G- q [; ?
# E$ f/ x0 {9 s【数据范围】/ q: x3 O3 y( T
0 }; d. G5 J' N" c 1≤n,m≤100
, O- J5 {+ @/ _0 M& C% L% v
7 D- e8 b3 i" n8 |) h) c) ~【输入样例】
- k, T. |5 n# O+ g+ [( b0 ?
. d% O* S; O2 w! W" Q3 \+ C2 [, N- v5 55 O0 O3 p# d' X0 d
0 1 0 0 0& n1 Z6 i9 R# v/ j3 _* d0 |1 x
0 1 0 1 0* @6 M# j' q$ ^* m9 l
0 0 0 0 0
: M) E4 p3 ~6 | W! O0 1 1 1 0
( `. y, C; u+ b( `4 a0 0 0 1 0
- m: n( ?& }0 X ]9 Y) y& G; }6 t【输出样例】5 \+ v; C+ N* t& r& a7 X! ~0 s& O
% `/ @4 o- I+ n
84 \' k( S+ x( |
【解题思路】
+ v- a, {; e: T; \. Y; N
! |4 K( ~2 D& Y! S BFS的典中典。- from collections import *
1 }& m1 ?( Z% b1 u3 b# K j\" h - n,m = map(int,input().split())
4 i9 ~: f0 D7 U1 M\" Y+ m - mp = [[0]*(m+5)]7 a/ r6 D; h0 a- F$ ~6 }/ }# D; V. ?
- for i in range(n):
: l/ J }# `, L( b! C - mp.append([0]+list(map(int,input().split())))
$ `8 ]3 a. F1 n; f - dir = [(1,0),(-1,0),(0,1),(0,-1)]$ a; A. `% }- W3 N T
- st = [[0]*(m+5) for _ in range(n+5)]: k6 O& u* |/ P @8 q
- def bfs():, B7 r6 W* K* [, _4 U
- q = deque()
# c\" p; X! z e - q.append([1,1,0]); z* C. _2 B# L5 f- Q5 D9 M( J* m
- st[1][1]=16 d: w6 U' P8 F6 e5 ?5 f8 j% n
- while q:: i/ Z, g. o5 \: S, B
- tx,ty,step = q.popleft() D* d2 o; D) ~$ L
- if tx==n and ty==m:
, a# m }# H1 ]8 M8 Y# q - print(step)9 N1 d8 ?# l1 P7 f9 s! s( S
- return \. c: s1 `7 c1 f; R
- for x_,y_ in dir:) W* c! @' c5 L: q* F) v) L8 c
- nx,ny = tx+x_,ty+y_. U( U; x0 T* e
- if nx<1 or nx>n or ny<1 or ny>m:continue
& k3 C$ U' q5 f/ f) m\" M - if mp[nx][ny]==1 or st[nx][ny]:continue
8 T: O1 T) Z% N) r% W4 N8 ]2 |/ i - q.append( [nx,ny,step+1] )5 F8 Z8 S% W! x0 H2 O6 L
- st[nx][ny]=1
4 r- ~; T+ A- E. }& }5 x - bfs()
复制代码
" @) c: `, |9 N |
zan
|