| Final round of the X Vologda Regional Informatics Olympiad for the Governors Prize 2025, grades 9-10 |
|---|
| Finished |
A maze of size $$$N \times M$$$ cells is given. In the upper left corner of the maze, there is a square with a side length of $$$P$$$ cells. In one step, the square can move one cell up, down, right, or left, provided it does not collide with occupied cells. You need to find the shortest possible path length for the square to reach the lower right corner.
The first line contains three numbers $$$N$$$, $$$M$$$, $$$P$$$. Next, there are $$$N$$$ lines of $$$M$$$ characters representing the cells of the maze: '.' if the cell is free, 'X' if it is occupied. It is guaranteed that the upper left and lower right $$$P \times P$$$ squares do not contain occupied cells.
Output the shortest possible path length, or $$$-1$$$ if such a path does not exist.
5 5 2...XX....XX...XXX...XX...
6
5 5 2...XX...XXXX.XXXX...XX...
-1
Subtask 1 (up to 20 points): $$$1 \leq N,M \leq 10$$$, $$$P = 1$$$
Subtask 2 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$P = 1$$$
Subtask 3 (up to 20 points): $$$1 \leq N,M \leq 50$$$, $$$P = 2$$$
Subtask 4 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq \min(50,N,M)$$$
Subtask 5 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq \min(N,M)$$$
| Name |
|---|


