← 返回题目列表

Codeforces · 250/E

E. 疯狂的乔

中文机器翻译题面 查看原题

乔在互联网上受到了伤害。现在他正在房子里肆虐,摧毁了他所经过的一切。

Joe 的房子有 n 层,每层都是 m 个单元格的一部分。每个单元要么什么也不包含(它是一个空单元),要么有砖墙或混凝土墙(总是三者之一)。据信,每层楼的左右两侧都被混凝土墙包围。

现在乔在第 n 层,第一个牢房,从左到右数。在每一时刻,乔都有他的目光方向,向右或向左(总是两个方向之一)。最初,乔向右看。

乔通过特定的算法移动。他每秒都会进行以下操作之一:

- 如果乔正下方的单元格是空的,那么乔就会摔倒。也就是说,他移动到这个牢房时,注视方向被保留。
- 否则考虑当前注视方向的下一个单元格。 如果单元格是空的,那么乔就会移入其中,凝视方向将被保留。 如果这个牢房里有砖块,那么乔就会用额头打碎它们(牢房变空),并将视线方向转向相反的方向。 如果这个牢房有混凝土墙,那么乔只需将视线方向转向相反的方向(混凝土可以承受任意数量的额头撞击)。

乔一到达一楼的任何牢房就会平静下来。

下图显示了 Joe 在房子周围的活动示例。

确定乔需要多少秒才能平静下来。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 100, 1 ≤ m ≤ 104)。

接下来的 n 行包含对 Joe 房子的描述。这些行中的第 i 行包含对房屋第 (n - i + 1) 层的描述——一行由 m 个字符组成:“.”表示空单元格,“+”表示砖块,“#”表示混凝土墙。

保证第n层第一个单元格是空的。

输出

打印一个数字——乔到达一楼所需的秒数;否则,如果它永远不会发生,则打印单词“Never”(不带引号)。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

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

输出 #1

14

输入 #2

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

输出 #2

42

输入 #3

2 2
..
++

输出 #3

Never