P9866 [POI 2021/2022 R2] bom

Translated from [POI2021~2022R2 Day2T1](https://szkopul.edu.pl/problemset/problem/MfTrGDTrlrVX21vwwhgsjaLv/statement/). Time limit: sub1 and sub4 8 s, sub2 2 s, sub3 3 s.

You are given an $n \times n$ grid that contains only `.`, `X`, `P`, `K`, `#`, with the following meanings: - `P` is the starting point. - `K` is the destination. - `.` is a passable cell. - `X` is an impassable rock wall. - `#` is an impassable brick wall. You also have one bomb. You choose a cell that is not a rock wall to place it. When it explodes, the explosion spreads from the original cell in the four directions (up, down, left, right), continuing step by step until, in that direction, it hits a rock wall or goes out of the grid. All cells in the explosion area become empty ground, but rock walls do not change. Then you need to find the shortest path from the start to the destination.

The first line contains an integer $n\ (2 \leq n \leq 1000)$. Then follows an $n \times n$ character matrix describing the grid.

If, after placing and detonating the bomb, a solution exists, output three lines: - Line 1: the length of the shortest path. - Line 2: the bomb placement position. - Line 3: one shortest path that satisfies the conditions (where `G` means up, `D` means down, `L` means left, `P` means right). If there is no solution, output `NIE`.

Explanation of the sample:  The subtasks are as follows: | Subtask ID | Special property | Score | | :-----------: | :-----------: | :-----------: | | $1$ | No brick walls | $10$ | | $2$ | $n \leq 50$ | $20$ | | $3$ | $n \leq 200$ | $30$ | | $4$ | No additional constraints | $40$ | Translated by ChatGPT 5