Mad Joe

题意翻译

乔乔被互联网上的喷子气到了。乔乔很愤怒。 乔乔的房子有 $n$ 楼，每个楼层由 $m$ 个单元组成。每个单元是空房或砖头或一堵墙。每层楼的左边和右边都有一堵墙。 乔乔最开始向右看。 现在乔乔在第 $n$ 层的第一个单元，他按以下方式移动。 - 如果乔乔的正下方的单元格是空的，那么乔乔就会移动到这个单元，注视方向不变。 - 否则就考虑在当前移动方向的下一个单元。 - 如果这个单元格是空的，那么乔乔就会移动到这个单元格，注视方向不变。 - 如果这个单元有砖头，那么该单元变为空单元，并且乔乔改变注视方向。 - 如果这个单元有一堵混凝土墙，那么乔乔只会改变注视方向。 确定乔乔需要多少秒才能到达第一层（任何一间房）。 第一行包含两个整数 $n$ 和 $m$（$2\leq n\leq 100，1\leq m\leq 10^4$）。 接下来的 $n$ 行包含对乔乔的房子的描述。其中第 $i$ 行包含房子的第（$n-i+1$）层的描述,这一行由 $m$ 个字符组成。". "表示一个空单元，"+"表示砖头，"/#"表示混凝土墙。 可以保证第 $n$ 层的第一个单元是空的。 输出乔乔到达第一层所需的最少秒数；如果无法到达，输出 "Never"。

题目描述

Joe has been hurt on the Internet. Now he is storming around the house, destroying everything in his path. Joe's house has $ n $ floors, each floor is a segment of $ m $ cells. Each cell either contains nothing (it is an empty cell), or has a brick or a concrete wall (always something one of three). It is believed that each floor is surrounded by a concrete wall on the left and on the right. Now Joe is on the $ n $ -th floor and in the first cell, counting from left to right. At each moment of time, Joe has the direction of his gaze, to the right or to the left (always one direction of the two). Initially, Joe looks to the right. Joe moves by a particular algorithm. Every second he makes one of the following actions: - If the cell directly under Joe is empty, then Joe falls down. That is, he moves to this cell, the gaze direction is preserved. - Otherwise consider the next cell in the current direction of the gaze. - If the cell is empty, then Joe moves into it, the gaze direction is preserved. - If this cell has bricks, then Joe breaks them with his forehead (the cell becomes empty), and changes the direction of his gaze to the opposite. - If this cell has a concrete wall, then Joe just changes the direction of his gaze to the opposite (concrete can withstand any number of forehead hits). Joe calms down as soon as he reaches any cell of the first floor. The figure below shows an example Joe's movements around the house. Determine how many seconds Joe will need to calm down.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2<=n<=100 $ , $ 1<=m<=10^{4} $ ). Next $ n $ lines contain the description of Joe's house. The $ i $ -th of these lines contains the description of the $ (n-i+1) $ -th floor of the house — a line that consists of $ m $ characters: "." means an empty cell, "+" means bricks and "\#" means a concrete wall. It is guaranteed that the first cell of the $ n $ -th floor is empty.

输出格式

Print a single number — the number of seconds Joe needs to reach the first floor; or else, print word "Never" (without the quotes), if it can never happen. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

3 5
..+.#
#+..+
+.#+.

输出样例 #1

14

输入样例 #2

4 10
...+.##+.+
+#++..+++#
++.#++++..
.+##.++#.+

输出样例 #2

42

输入样例 #3

2 2
..
++

输出样例 #3

Never