题目描述

Tossed by the storm on a deserted island, Robinson built himself a boat so that he could go out to the sea and seek out human domicile.

He is an experienced sailor, therefore he built the boat with accordance to the rules of craftsmanship: it has a longitudinal axis of symmetry and an appropriate shape. The boat's prow is thin, and it widens gradually towards the boat's centre, only to gradually narrow once again towards the stern.

In particular, at some point in the middle the boat is wider than both at the prow and stern.

Unfortunately, Robinson has launched his boat in a most improper space: there is extremely thick reed all around. It is, moreover, so stiff that the boat cannot break through. Perhaps Robinson can get to the high seas by carefully manoeuvring between the reed.

Due to lack of manoeuvrability, the boat can move forward and backward and even sidewards (leftward or rightward), but it cannot turn.

It is thus allowed, and may be in fact necessary, that the boat moves with its stern or broadside to the front.

You are to judge if Robinson can get to the high seas.

To make your task easier the island and its surroundings will be represented by a square map divided into square unit fields, each occupied by either water, part of Robinson's boat or an obstacle, eg.

land or reed. Initially the boat is set parallel to one of the cardinal directions, ie. its longitudinal axis of symmetry is parallel to this direction and the axis bisects the unit fields it is covered with.

We assume that the high seas starts where the map ends.

Hence Robinson may get to the high seas if his boat can leave the area depicted in the map.

A single move consists in moving the boat to a side-adjacent field in a chosen direction (north, south, east or west).

The move is permissible if both before and after it the boat remains entirely in water (it does not occupy a field with an obstacle).

Task You are to write a programme that reads the map's description from the standard input, calculates the minimum possible number of boat's moves that suffice to completely leave the area depicted in the map, writes out this number to the standard output.

被风暴抛弃在荒岛上的鲁滨逊（又译鲁滨孙）自己造了一条船，这样他就可以出海去寻找有人类居住的地方。

他是一位经验丰富的水手，因此他根据技术规程建造了它。它有一条纵向的对称轴，以及适于航行的外形：船头较尖，向船中逐渐扩宽，到船尾又逐渐收窄。

特别的是，船中的一些点比船头和船尾都宽。

可是很不幸，鲁滨逊在最不合适的位置让他的船下了水：周围有极其厚的芦苇。此外，这条船太僵硬以至于它无法突破芦苇。不过或许鲁滨逊可以通过在芦苇中小心翼翼地操纵船去往公海。

由于船太不灵活，船可以前进、后退甚至横着（向左或向右）移动，但它不能掉头。

允许船的船尾或者船舷在前进行移动，事实上这可能是必要的。

你需要判断鲁滨逊是否可以到达公海。

为了简化你的工作，岛屿和周围的环境将由一张划分成方格的正方形地图表示，每格只可能是水、鲁滨逊船的一部分或障碍物（比如说岛屿和芦苇）。最初船平行于一个主要方向（换句话说，即其纵向对称轴平行于此方向且其平分其覆盖的方格）

我们假定地图之外就是公海。

因此，如果他的船可以离开地图描绘的区域，鲁滨逊也许就能到达公海了。

一步表现为船往选定的方向（北，南，东或西）移动一格。

如果移动前后的船保持整个在水中（不占据任何有障碍物的格子），那么这个移动是合法的。

你的任务是编写一个程序，从标准输入中读取地图的描述，计算船离开地图描述的区域的最少步数，并输出至标准输出。

输入格式

The first line contains one integer $3\le n\le 2000$, denoting the length of the map's side.

In each of the following $n$ lines there are $n$ characters describing successive fields of the map:

$i^{th}$ character in the $(j+1)^{th}$ line tells the contents of the field $(i,j)$.

The following characters may appear there:

"." - (dot) denotes a field filled with water, "X" - denotes an obstacle (land or reed), "r" - denotes a part of Robinson's boat. 第一行一个正整数 $$3\le_n\le_2000$,$ 表示地图的边长。

接下来 $n$ 行每行 $n$ 个字符表示地图：（此处省略两张图片）第 $(j+1)$ 行的的第 $i$ 个字符表示方格 $(i,j)$。以下的字符可能会在输入中出现：.表示一格水，X 表示一格障碍物（岛屿或芦苇），R 表示鲁滨孙的船的一部分。

输出格式

Your programme should write out (in the first and only line of the standard output) a single positive integer, equal to the minimum number of boat's moves that suffice to completely leave the area depicted in the map.

Should getting to the high seas be impossible, write out the word 'NIE' ('no' in Polish).

你的程序应当输出（在标准输出的第一行且仅有一行）一格正整数表示鲁滨逊的船完全离开地图标示的区域需要的最小步数。

如果鲁宾逊无法到达公海，输出一行 NIE（波兰语中否定的意思）

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

10