1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

把“蛋仔静止的位置”看成图上的一个点。 每次从某个静止点出发,任选一个方向开始滚动,直到再次停下,这整个过程都只算 1 次滚动,因此这是一个典型的最短路分层问题,直接用 BFS 求最少滚动次数。

难点在于如何正确模拟“一次滚动”:

  1. 蛋仔遇到障碍物 # 或地图外侧虚拟障碍时会停下。
  2. 蛋仔进入挡板 / 或 \ 后会立刻改变方向继续滚动,不能停在挡板上。

P4579.第2题-蛋仔滚动

    1000ms Tried: 107 Accepted: 16 Difficulty: 7 所属公司 : 网易
    算法与标签>BFS

题目描述

给定一个mmm行nnn列的地图,蛋仔从起点(sr,sc)(sr,sc)(sr,sc)出发,需要到达终点(er,ec)(er,ec)(er,ec)。

蛋仔每次可以选择向上、下、左、右四个方向之一开始滚动。一旦开始滚动,在遇到阻挡前无法主动停下。为了防止蛋仔滚出地图,地图外侧视为额外包裹了一圈障碍物。

地图中有三类特殊格子:#为障碍物,蛋仔不能进入;/为斜挡板;\为反斜挡板。题目保证起点和终点所在格子均不是特殊格子,给出的特殊格子坐标互不重复。

挡板本身占据一个格子,蛋仔进入挡板格后会立即根据挡板类型改变方向并继续滚动。/型挡板:从左侧进入改为向上,从右侧进入改为向下,从上方进入改为向左,从下方进入改为向右。\型挡板:从左侧进入改为向下,从右侧进入改为向上,从上方进入改为向右,从下方进入改为向左。

补充说明:一次“滚动"定义为从某个静止位置出发,选择一个方向,直到再次停下为止,即使途中多次改变方向也只记为111次滚动。若蛋仔即将进入某个挡板格,但按挡板规则计算出的出口方向对应的下一格是障碍物或另一个挡板,则该挡板视为不可进入,蛋仔停在进入挡板前的那一格。只要蛋仔在某次滚动过程中经过终点格,就视为成功到达,不要求恰好停在终点。若蛋仔在挡板间无限反弹且经过了终点,仍视为可以到达。

请求出蛋仔从起点到终点的最少滚动次数,若无法到达输出−1-1−1。

输入描述

第一行输入两个整数 m,n(1<m,n<100)m,n(1<m,n <100)m,n(1<m,n<100),表示地图的行数和列数。

第二行输入一个整数k(0<k<10000) k(0 <k< 10000)k(0<k<10000),表示特殊格子的数量。

接下来 kkk行,每行输入三个值r,c,chr,c,chr,c,ch,表示第rrr行第ccc 列是一个特殊格子,类型为 chchch(#、/或\ )。

接下来一行输入两个整数 sr,sc(1<sr≤m,1≤sc≤n)sr,sc(1< sr ≤ m,1≤ sc ≤n)sr,sc(1<sr≤m,1≤sc≤n),表示起点坐标。

最后一行输入两个整数 er,ec(1<er<m,1<ec<n)er,ec(1< er < m,1< ec <n)er,ec(1<er<m,1<ec<n),表示终点坐标。所有坐标均为1−based 1-based1−based。

输出描述

输出一个整数,表示蛋仔到达终点的最少滚动次数;若无法到达,输出−1-1−1。

样例1

输入

3 5
3
1 3 #
1 5 \
2 5 /
2 1
2 3

输出

1

说明

地图如下(sss 为起点,EEE为终点,外圈为虚拟障碍物):

#######
#..#.\#
#S.E./#
#.....#
#######

蛋仔从起点向右滚动111次,滚动过程中经过终点,答案为 111。

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 3, 168ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?