[POI 2021/2022 R2] bom

Luogu

IDLGP9866

Time8000ms

Memory300MB

DifficultyP5

POI（波兰）20212022Special Judge

你有一个 $n \times n$ 的图，仅包含 `.`、`X`、`P`、`K`、`#`，意义如下： - `P` 起点。 - `K` 终点。 - `.` 可以通过的路。 - `X` 不可以通过的岩石墙。 - `#` 不可以通过的砖墙。你还有一枚炸弹，你选择一个不是岩石墙的地方放置，爆炸时，会从原来的地方上下左右依次扩散爆炸直到某一方向碰到了岩石墙或超出了图的范围。爆炸区域变为空地，但岩石墙不会。然后你需要求出起点至终点的最短路径。 ## Input 第一行一个整数 $n\ (2 \leq n \leq 1000)$。然后 $n \times n$ 大小的字符矩阵，描述了图。 ## Output 如果放置完炸弹并引爆后有解，则输出三行： - 第一行：最短路径长度。 - 第二行：放置炸弹位置。 - 第三行：其中符合条件的最短路径（其中 `G` 表示向上，`D` 表示向下，`L` 表示向左，`P` 表示向右）。若无解，输出 `NIE`。 [samples] ## Background 翻译自 [POI2021~2022R2 Day2T1](https://szkopul.edu.pl/problemset/problem/MfTrGDTrlrVX21vwwhgsjaLv/statement/)。时限：sub1 和 sub4 8s，sub2 2s, sub3 3s。 ## Note 样例解释： ![](https://cdn.luogu.com.cn/upload/image_hosting/v7jk5v8b.png) 子任务分配如下： | 子任务编号 | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | | $1$ | 不含砖墙 | $10$ | | $2$ | $n \leq 50$ | $20$ | | $3$ | $n \leq 200$ | $30$ | | $4$ | 无特殊限制 | $40$ |

Samples

Input #1

6
......
.X.##.
..#.X.
..X.#K
.P#.X#
.X....

Output #1

9
2 3
GGPPGPPDD

API Response (JSON)

{
  "problem": {
    "name": "[POI 2021/2022 R2] bom",
    "description": {
      "content": "你有一个 $n \\times n$ 的图，仅包含 `.`、`X`、`P`、`K`、`#`，意义如下： - `P` 起点。 - `K` 终点。 - `.` 可以通过的路。 - `X` 不可以通过的岩石墙。 - `#` 不可以通过的砖墙。 你还有一枚炸弹，你选择一个不是岩石墙的地方放置，爆炸时，会从原来的地方上下左右依次扩散爆炸直到某一方向碰到了岩石墙或超出了图的范围。   爆炸区域变为空地，但岩",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 307200
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9866"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一个 $n \\times n$ 的图，仅包含 `.`、`X`、`P`、`K`、`#`，意义如下：\n\n- `P` 起点。\n- `K` 终点。\n- `.` 可以通过的路。\n- `X` 不可以通过的岩石墙。\n- `#` 不可以通过的砖墙。\n\n你还有一枚炸弹，你选择一个不是岩石墙的地方放置，爆炸时，会从原来的地方上下左右依次扩散爆炸直到某一方向碰到了岩石墙或超出了图的范围。  \n爆炸区域变为空地，但岩...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments