Codeforces Round 234 (Div. 2) |
---|
Закончено |
Инна очень любит сладкое и игру «Матрица конфет». Сегодня она придумала новую игру — «Матрица конфет 2: перезагрузка».
Поле для новой игры представляет собой прямоугольную таблицу размера n × m. В каждой строке этой таблицы одна клетка занята фигуркой гномика, одна клетка занята конфеткой, остальные клетки строки свободны. Игра длится несколько ходов. На каждом ходе игрок должен выбрать все строки матрицы, в которых гномики не стоят в конфетах, и крикнуть: «Побежали!». После чего все гномики в выбранных строках начинают синхронно передвигаться вправо. За одну секунду каждый гномик шагает в соседнюю клетку, которая находится правее его текущей клетки. Передвижения продолжаются до тех пор пока не случится одно из событий:
Цель игры — сделать так, чтобы все гномики находились в клетках с конфетами.
Инна — большой молодец, ведь она придумала такую интересную игру. А как же вы? Ваша задача — сыграть в эту игру оптимальным образом. А именно, по заданному игровому полю сказать, какое минимальное количество ходов потребуется игроку, чтобы добиться цели игры.
Первая строка входных данных содержит два целых числа n и m (1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000).
Следующие n строк содержат по m символов — поле для игры в «Матрица конфет 2: перезагрузка». Символ «*» обозначает свободную клеточку поля, символ «G» — фигурку гномика, а символ «S» — конфету. Других символов матрица не содержит. Гарантируется, что каждая строка содержит ровно один символ «G» и один символ «S».
В единственной строке выведите целое число — минимальное количество ходов, необходимое для достижения цели игры, либо -1, если достичь ее на данном игровом поле невозможно.
3 4
*G*S
G**S
*G*S
2
1 3
S*G
-1
Название |
---|