← 返回题目列表

Codeforces · 400/B

B. Inna 和新糖果矩阵

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

Inna 喜欢糖果和一个叫做“糖果矩阵”的游戏。今天,她想出了新游戏《糖果矩阵2:重装上阵》。

新游戏的场地是一个大小为 n × m 的矩形桌子。表格的每一行包含一个带有矮人雕像的单元格,一个带有糖果的单元格,该行的其他单元格为空。游戏持续数步。在每次移动过程中,玩家应该选择矩阵中矮人不在糖果单元格上的所有行,并大喊“走吧!”。之后,所选行的所有矮人开始同时向右移动。在每一秒中,每个矮人都会前往位于其当前单元格右侧的相邻单元格。该运动将持续进行,直到发生以下事件之一:

- 所选行之一中的某个矮人位于该行最右边的单元格中;
- 所选行中的一些矮人位于有糖果的单元格中。

游戏的重点是将所有矮人运送到糖果格中。

Inna 太棒了,她想出了这么有趣的游戏。但你呢?你的任务就是以最佳状态玩好这个游戏。具体来说,您应该根据给定的游戏字段说明玩家需要多少步才能达到游戏目标。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000)。

接下来的 n 行每行包含 m 个字符 - “Candy Martix 2:Reload”的游戏字段。字符“*”代表该字段的空单元格,字符“G”代表矮人,字符“S”代表糖果。该矩阵不包含其他字符。保证每一行恰好包含一个字符“G”和一个字符“S”。

输出

在一行中打印一个整数 - 要么是实现游戏目标所需的最小移动数,要么是 -1(如果在给定的游戏场上无法实现目标)。

示例

输入 #1

3 4
*G*S
G**S
*G*S

输出 #1

2

输入 #2

1 3
S*G

输出 #2

-1