[蓝桥杯 2018 国 C] 迷宫与陷阱

Luogu

IDLGP8673

Time3000ms

Memory256MB

DifficultyP3

2018广度优先搜索 BFS图论建模蓝桥杯国赛

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 $N \times N$ 个格子组成的二维迷宫。小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。迷宫中有些格子小明可以经过，我们用 `.` 表示；有些格子是墙壁，小明不能经过，我们用 `#` 表示。此外，有些格子上有陷阱，我们用 `X` 表示。除非小明处于无敌状态，否则不能经过。有些格子上有无敌道具，我们用 `%` 表示。当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 $K$ 步。之后如果再次到达该格子不会获得无敌状态了。处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。给定迷宫，请你计算小明最少经过几步可以离开迷宫。 ## Input 第一行包含两个整数 $N$ 和 $K$。$(1 \le N \le 1000，1 \le K \le 10)$。以下 $N$ 行包含一个 $N\times N$ 的矩阵。矩阵保证左上角和右下角是 `.`。 ## Output 一个整数表示答案。如果小明不能离开迷宫，输出 $-1$。 [samples] ## Note 时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

Samples

Input #1

5 3
...XX
##%#.
...#.
.###.
.....

Output #1

Input #2

5 1
...XX
##%#.
...#.
.###.
.....

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2018 国 C] 迷宫与陷阱",
    "description": {
      "content": "小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 $N \\times N$ 个格子组成的二维迷宫。 小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。 每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。 迷宫中有些格子小明可以经过，我们用 `.` 表示； 有些格子是墙壁，小明不能经过，我们用 `#` 表示。 此外，有些格子上有陷阱，我们用 `X` 表",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8673"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 $N \\times N$ 个格子组成的二维迷宫。\n\n小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。\n\n每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。\n\n迷宫中有些格子小明可以经过，我们用 `.` 表示；\n\n有些格子是墙壁，小明不能经过，我们用 `#` 表示。\n\n此外，有些格子上有陷阱，我们用 `X` 表...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments