407780: GYM102892 9 Plane and Simple

You work at an airport, and you just received the baggage for a recently arrived flight, consisting of $$$k$$$ bags. You are in charge of placing these bags on the conveyor belt in the airport, which can be represented as a single, non self-intersecting ring.

Due to the COVID-19 pandemic, however, you want to place everyone's bags far apart on the conveyor belt.

Your task is to find the maximum distance $$$d$$$, such that it's possible to place all of the bags on the conveyor belt, and all of the bags that are next to each other on the conveyor belt will be at least $$$d$$$ units apart at all times during the conveyor belt's rotation. Assume that all parts of the conveyor belt move at the same speed.

Two bags are considered to be "next to each other" on the conveyor belt if you could travel from one bag to the other either clockwise or counter-clockwise on the conveyor belt, without encountering any other bags.

Note that in this problem, distance is measured in "Manhattan Distance", i.e. the Manhattan Distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is calculated as $$$\lvert x_2 - x_1\rvert + \lvert y_2 - y_1\rvert$$$.

The first line of input contains two space-separated positive integers $$$n$$$ $$$(1 <= n <= 200)$$$ and $$$k$$$ $$$(2 <= k <= 400)$$$: the length and width of the room that the baggage claim conveyor belt is in, and the number of bags on the upcoming flight, respectively.

The next $$$n$$$ lines contain $$$n$$$ characters each, representing the layout of the room. An "x" character represents part of the conveyor belt, while a "." character represents empty space.

The conveyor belt will be at most 400 characters long, i.e. there will be at most 400 "x" characters in the grid. The conveyor belt will also always be at least $$$k$$$ characters long.

The conveyor belt is guaranteed to be a single non-self-intersecting ring. Additionally, every conveyor belt space (every "x" character) will be directly adjacent (not diagonally) to exactly two other conveyor belt spaces.

Output a single positive integer $$$d$$$: the maximum distance, such that it's possible to place all of the bags on the conveyor belt at least $$$d$$$ units apart (in manhattan distance) at all times during the rotation of the conveyor belt.

Subtask 1 (15 points): there will be at most 15 $$$x$$$ characters in the input

Subtask 2 (61 points): no additional constraints

7 3
.......
..xxxx.
..x..x.
.xx..x.
.x...x.
.xxxxx.
.......

3

10 2
..........
.xxxxxxxx.
.x......x.
xx......x.
x.......x.
x..xxxx.x.
x.xx..x.x.
xxx...xxx.
..........
..........

5

11 2
xxxxxxxxxx.
x........x.
xxxxxxxx.x.
.......x.x.
xxxxxxxx.x.
x........x.
xxxxxxxx.x.
.......x.x.
xxxxxxxx.x.
x........x.
xxxxxxxxxx.

7