Description

Tossed by a storm onto a deserted island, Robinson built himself a boat so that he could go out to sea and look for human habitation.

He is an experienced sailor, so he built the boat according to the rules of craftsmanship: it has a longitudinal axis of symmetry and an appropriate shape. The prow is thin, the hull widens gradually toward the middle, and then it narrows again toward the stern. In particular, at some point in the middle the boat is wider than both at the prow and at the stern.

Unfortunately, Robinson launched his boat in the worst possible place: there is extremely thick reed all around. Moreover, it is so stiff that the boat cannot break through. Perhaps Robinson can reach the high seas by carefully maneuvering between the reeds.

Because the boat is not very maneuverable, it can move forward, backward, and even sideways (left or right), but it cannot turn. It is therefore allowed—and may even be necessary—for the boat to move with its stern or with its broadside leading.

You are to determine whether Robinson can reach the high seas.

To make the task precise, the island and its surroundings are represented by a square map divided into unit square cells. Each cell is either water, a part of Robinson’s boat, or an obstacle (e.g., land or reed). Initially, the boat is aligned with one of the cardinal directions, that is, its longitudinal symmetry axis is parallel to that direction and bisects the unit cells it covers.

We assume that the high seas begin beyond the edge of the map. Hence, Robinson can reach the high seas if his boat can completely leave the area depicted on the map.

A single move consists of shifting the boat by one cell in one of the four directions: north, south, east, or west. A move is permissible if both before and after the move the boat is entirely on water (i.e., it does not occupy any cell with an obstacle).

Task: Write a program that reads the map from standard input, computes the minimum number of moves needed for the boat to completely leave the map, and writes this number to standard output.

Input Format

• The first line contains a single integer $n$ with $3 \le n \le 2000$, denoting the side length of the map.

• Each of the following $n$ lines contains $n$ characters describing the map. The $i^{\text{th}}$ character in the $(j+1)^{\text{th}}$ line describes cell $(i, j)$. The characters are:

  • "." a cell of water,
  • "X" an obstacle (land or reed),
  • "r" a part of Robinson’s boat.

Output Format

Output a single positive integer: the minimum number of moves needed for the boat to completely leave the map. If it is impossible to reach the high seas, output NIE.

10
..........
..........
..r.......
.rrrX.....
rrrrr.....
.rrr......
X.r.......
.Xr.......
..........
..........

10

Hint

Translated by ChatGPT 5