- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
题目描述】
; t) n0 u$ L! R
( W' p" f+ G! i5 i* {1 H, L- D 给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 (n,m)处,至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。3 c! { [% H# _) y
: z# _3 m, G9 ^0 {/ U4 O' u5 k【输入格式】
7 b3 {( ^; h: K$ X: c; P' q# J- `( a' a2 F- n
第一行包含两个整数 n 和 m。
* k9 z. [6 X- k, x$ J2 u6 y% [1 T/ m! H9 v) y; L% `
接下来 n行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
2 {8 C0 k+ C Q ~ Q2 l: \, M
6 q3 u, Q3 c$ h3 l4 x- A+ O【输出格式】. R- G7 c' A G: [! w+ q0 p/ h
3 c, d: z5 J- b' X& |2 G
输出一个整数,表示从左上角移动至右下角的最少移动次数。
! v6 J) b b q) }- X
' O2 k; J7 s5 i7 @, G! n! k0 B5 _' I【数据范围】. b/ ~/ X* h; T2 T7 i9 P" e* x
; e! |2 B+ J& A3 U3 g( i 1≤n,m≤1008 V! c8 S- C- E1 |8 b; X! [
' z. f* A! _9 q
【输入样例】
! X# P1 N: A" B a& `! D2 ~. m+ |8 @, R$ I& L1 B$ X
5 56 r+ j) t0 `1 {! k/ E" {' f/ P
0 1 0 0 0, d! L; J9 e" E2 D" t" y
0 1 0 1 0
+ A! ~8 c& m+ D* c! \ e1 U0 0 0 0 0
; ]/ R8 I# v1 R( a$ u+ E! ~, \0 1 1 1 0. u9 t( e3 ]8 T. R6 [
0 0 0 1 0
& `# ^3 Z0 B: j1 H: q. u【输出样例】
: ` a* m* o8 D* v) b- I0 g- C% D& m$ c* Y$ E
8
$ N1 L; E3 u! { 【解题思路】* M* M1 F+ F4 s7 K% q" T
" W& p D5 o9 ? BFS的典中典。- from collections import *# T' {3 [\" Q3 j\" q0 \, f! G
- n,m = map(int,input().split())\" b! A* E2 [% t+ O3 w
- mp = [[0]*(m+5)]
! k) C* i$ K9 c; P. [4 a/ X - for i in range(n):
& g8 G. C0 |) b - mp.append([0]+list(map(int,input().split())))- m7 W: Y; T# t8 m( S+ M
- dir = [(1,0),(-1,0),(0,1),(0,-1)]
9 T1 b/ G. ?- W, _% ?) a4 I - st = [[0]*(m+5) for _ in range(n+5)]: B4 i! q. z/ r& h. l
- def bfs():
# z\" X L9 d/ @2 D$ z0 o - q = deque()
4 `( X. ^9 d& `' O9 Z4 Z# y - q.append([1,1,0])3 R& y p8 A3 j\" ?3 }
- st[1][1]=1
5 A8 G) d' e9 t6 \% U8 q - while q:
- }5 y# |9 F* S( |( [; U\" }7 F - tx,ty,step = q.popleft()5 l! B% j8 e& b {
- if tx==n and ty==m:\" [% y4 P* l5 [* S3 Y' y, H+ A$ v
- print(step)* `2 U/ {2 [* Y. T: N
- return
& B# Y: `, o3 B - for x_,y_ in dir:
; A, O8 X3 V4 w8 s4 v2 Y - nx,ny = tx+x_,ty+y_
7 j. \8 B5 N3 }) ` - if nx<1 or nx>n or ny<1 or ny>m:continue: ]$ L\" `* [4 ~. X
- if mp[nx][ny]==1 or st[nx][ny]:continue$ O1 Z. Z6 F1 i# o3 y
- q.append( [nx,ny,step+1] )
& J. m8 Q* q: [\" ^' T d - st[nx][ny]=12 \4 Y' f3 R6 v T\" \
- bfs()
复制代码
* S" [/ G$ o. C- T: c |
zan
|