Задача: Building a Ski Course
Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
RSRSSS
RSRSSS
RSRSSS
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.
ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
INPUT FORMAT:
* Строка 1: Два разделённых пробелом целых числа M и N.
* Строки 2..M+1: M строк ровно по N символов (каждый R или S),
описывающих желаемое финальное состояние поля.
OUTPUT FORMAT:
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.
| Ввод |
Вывод |
|
3 6
RSRSSS
RSRSSS
RSRSSS
|
3 |
OUTPUT DETAILS:
ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец, S в колонках 4-6.
Ваш ответ: