CF400B Inna and New Matrix of Candies

Inna 喜欢糖果和一款名为「Candy Matrix」的游戏。今天，她又想出了新游戏「Candy Matrix 2: Reload」。 新游戏的场地是一个大小为 $n \times m$ 的矩形表格。每一行中包含一个有小矮人玩偶的格子、一个有糖果的格子，其余格子为空。游戏进行若干步。每一步，玩家需要选择所有小矮人没有站在糖果格子的行，并喊出“Let's go!”。随后，这些被选中的行中的所有小矮人开始同时向右移动。每一秒钟，每个小矮人向其当前位置右侧的相邻格子移动一次。移动过程在下列任一事件发生时结束： - 某一被选中的行中，小矮人位于该行最右侧的格子； - 某一被选中的行中，小矮人位于有糖果的格子上。 游戏的目标是让所有小矮人都移动到糖果格子上。 Inna 是个天才，想出了如此有趣的游戏。但你能否将游戏玩到最优？具体来说，给定游戏场地，要求你计算玩家达到目标所需的最少操作次数。

输入第一行包含两个整数 $n$ 和 $m$，表示场地大小 $(1 \le n \le 1000;\ 2 \le m \le 1000)$。 接下来 $n$ 行，每行包含 $m$ 个字符，描述「Candy Matrix 2: Reload」的游戏场地。字符“*”表示该格为空，字符 “G” 表示小矮人，字符 “S” 表示糖果。保证每一行恰好有一个 “G” 和一个 “S” 字符。

输出一行，包含一个整数，表示达到目标所需的最少操作次数。如果场地无解，输出 $-1$。

由 ChatGPT 5 翻译