题目详情题解（0）讨论（0）提交记录（0）

AT_abc436_d.[ABC436D] Teleport Maze

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个由 HH 行 WW 列组成的迷宫。我们用 (i,j)(i,j) 表示从上往下第 ii 行、从左往右第 jj 列的格子。每个格子的类型由一个字符 Si,jS_{i,j} 给定，具体含义如下：

  • .：空格子
  • #：障碍格子
  • 小写英文字母（a - z）：传送格子

你可以不限次数、顺序进行以下两种操作：

  • 行走：从当前位置移动到相邻的上下左右四个方向的其中一个格子，但不能走到障碍格或出界。
  • 传送：当你在一个传送格上时，可以立刻移动到任何一个字符相同的传送格上。

请你判断是否可以从 (1,1)(1,1) 出发，移动到 (H,W)(H,W)。如果可以，请输出所需的最少操作次数；否则输出 −1-1。

输入格式

输入从标准输入读入，格式如下：

HH WW
S1,1S1,2…S1,WS_{1,1}S_{1,2}\dots S_{1,W}
⋮\vdots
SH,1SH,2…SH,WS_{H,1}S_{H,2}\dots S_{H,W}

输出格式

如果可以从 (1,1)(1,1) 到达 (H,W)(H,W)，输出所需的最少操作次数；否则输出 −1-1。

输入输出样例

  • 输入#1

    3 4
..a.
####
ba#b

    输出#1

    5

  • 输入#2

    3 4
..a.
####
b.#b

    输出#2

    -1

  • 输入#3

    4 4
xxxx
xxxx
xxxx
xxxx

    输出#3

    1

  • 输入#4

    7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.

    输出#4

    12

说明/提示

样例解释 1

如样例，你可以按如下顺序操作从 (1,1)(1,1) 到 (3,4)(3,4)：

  1. 从 (1,1)(1,1) 走到 (1,2)(1,2)。
  2. 从 (1,2)(1,2) 走到 (1,3)(1,3)。
  3. 从 (1,3)(1,3) 通过传送到 (3,2)(3,2)。
  4. 从 (3,2)(3,2) 走到 (3,1)(3,1)。
  5. 从 (3,1)(3,1) 通过传送到 (3,4)(3,4)。

共需要 55 次操作，为最少次数。

样例解释 2

无法从 (1,1)(1,1) 到达 (3,4)(3,4)。

数据范围

  • 1≤H,W≤10001\leq H,W \leq 1000
  • H×W≥2H\times W \geq 2
  • HH、WW 均为整数
  • Si,jS_{i,j} 只可能为 .、# 或小写英文字母
  • S1,1≠#S_{1,1} \neq \texttt{\#}
  • SH,W≠#S_{H,W} \neq \texttt{\#}

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页