题目描述

题目译自 XV OI Olimpiada Informatyczna – I etap Robinson

鲁滨逊因风暴被困荒岛，建造了一艘小船，决心驶向大海寻找人类居所。他是经验丰富的航海者，小船遵循工艺原则：沿纵轴对称，船首狭窄，向中部逐渐加宽，再向船尾收窄。尤其在中间某处，船宽超过首尾。

不幸的是，鲁滨逊下水处长满密实芦苇，坚韧无比，小船无法撞断或穿过。他需巧妙操控小船，争取驶入开放海域。由于小船机动性差，仅能前后左右移动，无法转弯，可能以船尾或侧舷向前。

你的任务是判断鲁滨逊能否驶出至开放海域。为简化问题，荒岛及其周围表示为一个正方形网格，划分为单位方格，每格可能是水、鲁滨逊小船的一部分或障碍（陆地或芦苇）。小船平行于四个基本方向之一，中心沿纵轴对称穿过一列单位方格。

假定网格外为开放海域。若小船整体离开网格区域，鲁滨逊即可驶出。每次移动为沿北、南、东、西方向移一格，移动前后小船需完全位于水域。

编写程序：

• 从标准输入读取网格描述。
• 计算小船完全驶出网格所需的最少移动次数。
• 将结果输出到标准输出。

输入格式

第一行包含一个整数 $n$ $(3 \leq n \leq 2000)$，表示网格边长。接下来的 $n$ 行，每行包含 $n$ 个字符，描述网格方格：第 $j+1$ 行的第 $i$ 个字符表示坐标 $(i,j)$ 的内容。可能字符包括：

• .：水域。
• X：障碍（芦苇或陆地）。
• r：鲁滨逊小船的一部分。

输出格式

输出一行，包含一个正整数，表示小船完全离开网格区域所需的最少移动次数。若无法驶出，输出 NIE。

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

10