Background

Translated from POI2021~2022R2 Day2T1.

Time limit: sub1 and sub4 8 s, sub2 2 s, sub3 3 s.

Problem Description

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.

Input Format

The first line contains an integer $n\ (2 \leq n \leq 1000)$.

Then follows an $n \times n$ character matrix describing the grid.

Output Format

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.

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

9
2 3
GGPPGPPDD

Hint

Explanation of the sample:

The subtasks are as follows:

Translated by ChatGPT 5