U413867 Y0136 泉州东西塔

春暖花开。 …… 我不明白，这路上的积雪，为何永久不化？ 只是等一个人。 等谁？ 你若明白，就爱上一个人吧。 …… 心中的冰雪，只有爱能融化。 给你爱，就是陪你走东西塔。 ——《茗城随笔》

泉州有两座塔，就是东西塔。 前来拜佛的人要从东塔走到西塔。为了节省时间以免误了飞机，chenlongli 非常着急，于是向 ggylz49 求助。 然而 ggylz49 很不幸地发现，路是 $n \times n$ 的图，且中间有很多小塔。东塔在图的左上角 $(0,0)$ 位置，西塔在右下角 $(n-1,n-1)$ 位置，这两个点在地图上用 `E` 表示，普通道路用 `L` 表示，小塔用 `N` 表示。两人初始的位置是东塔，目标位置是西塔。 ggylz49 不会 72 变，他和 chenlongli 每 $2$ 秒可以向右或向下移动一格，也就是从当前位置 $(x,y)$ 移动到 $(x+1,y)$ 或 $(x,y+1)$。如果该位置是小塔，则这个位置不能到达，否则佛祖会生气 ~~，ggylz49 和 chenlongli 会坠入阿鼻地狱，子孙 18 代不得好死~~。 于是 ggylz49 暴力算出了一种方案需要的时间。然而很不幸，这个时间会延误飞机。他需要找出所有方案，并计算最少的时间。 现在 ggylz49 很着急，请告诉他从东塔到西塔的最短时间（秒）。

第一行是一个数 $n$。 接下来 $n$ 行，每行 $n$ 个字符，代表这个点的状况。

一行一个整数，表示到达西塔的最短时间。

# $0 \le n \le 10^4$。 **保证有可行的解。** 保证字符为 `E`，`N`，`L` 之一。 **特别的，到达起点和终点的时间为 $0$**。 # ## 样例解释 解释中 $1$ 表示经过的点，$0$ 表示未经过的点。 # 有两条路线均为最短。 ```UPD 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 ``` ```XX 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 ``` 两种方案都经过 $5$ 个表示路的点，需要 $10$ 秒。 # endl。