Problem Description

Xiaoming is a big fat guy, or rather a very, very fat guy. If a normal person takes up an area of $1\times1$, Xiaoming needs an area of $5\times5$.

Because Xiaoming is too fat, it is very inconvenient for him to move. When playing some games, Xiaoming suffers a lot compared to his friends. Xiaoming’s friends made a plan to help him lose weight. The main idea of the plan is to take Xiaoming to play some games, so that he can exercise and burn fat during the games. Going through a maze is an important part of the plan.

The friends designed a maze. The maze can be seen as a square grid made of $n\times n$ small squares. A normal person occupies a $1\times1$ area in the grid at a time, while Xiaoming occupies a $5\times5$ area. Xiaoming’s position is defined as the very center cell of his body. There are obstacles around the entire maze. To make it easier for Xiaoming, the friends set the start at row $3$, column $3$, and the end at row $n-2$, column $n-2$.

Xiaoming starts at time $0$. In each unit of time, he can move $1$ unit up, down, left, or right from his current position, or stay where he is. Walking through the maze is very hard for Xiaoming. If he stays in the maze for a long time, because he burns a lot of fat, he will become a fat guy at time $k$, and then only occupy a $3\times3$ area. If he stays even longer, he will become a normal person at time $2\times k$, and then only occupy a $1\times1$ area. Note that when Xiaoming becomes thinner, the start and end positions of the maze do not change.

Please find the minimum time for Xiaoming to reach the end of the maze. Note that when Xiaoming reaches the end, he may have become thinner or may not have become thinner.

Input Format

The first line contains two integers $n$, $k$. Then there are $n$ lines, each line is a string of $n$ characters. The character + means empty ground, and the character * means an obstacle.

Output Format

Output one integer, the answer.

9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++

16

Hint

For $30\%$ of the test cases, $1 \leq n \leq 50$.

For $60\%$ of the test cases, $1 \leq n \leq 100$.

For all test cases, $1 \leq n \leq 300$, $1 \leq k \leq 1000$.

Lanqiao Cup 2019 National Contest, Group A Problem F (Group C Problem I).

Translated by ChatGPT 5