Задача . D. Царство и государство

Красная Шапочка и Иван Дурак внезапно обнаружили себя за тридевять земель, в мире, который представлен огромным цилиндром. На одном из оснований цилиндра (назовем его «верх цилиндра») вся поверхность занята некоторым царством, на другом основании (назовем его «низ цилиндра») вся поверхность занята некоторым государством, а боковая поверхность цилиндра целиком покрыта морем.

В один прекрасный день царь некоторого царства и государь некоторого государства решили, что не дело это морю пропадать зря, когда его можно превратить в землю и тем самым расширить границы своих владений. Для того, чтобы писари могли вести учет происходящего, море представили в виде сетки, состоящей из r строк и c столбцов — каждая ячейка этой сетки представляет некоторую прямоугольную область на стороне цилиндра. Строки занумерованы от 1 до r сверху вниз, а столбцы — от 1 до c слева направо. Две ячейки считаются смежными, если у них есть общая сторона. Кроме того, если две ячейки расположены в одной строке — одна в самом левом столбце, а другая — в самом правом, то они тоже смежны.

Изначально все ячейки покрыты морем. Теперь царь и государь планируют превратить часть из них в землю одна за одной согласно некоторому порядку, который Вам предоставлен.

Единственной проблемой на пути выполнения их плана является то, что по морю пролегает важный торговый маршрут. Поэтому в процессе превращения моря в землю Вы хотите, чтобы в каждый момент времени существовала последовательность ячеек, удовлетворяющих следующим свойствам (такую последовательность ячеек назовем торговым маршрутом):

• Все ячейки в последовательности являются морем (еще не превращены в землю).
• Первая ячейка в последовательности находится в первой строке (самой верхней).
• Последняя ячейка в последовательности находится в последней строке (самой нижней).
• Любые две последовательные ячейки в последовательности смежны друг с другом.

Красной Шапочке и Ивану Дураку поручили переработать план так, чтобы в любой момент времени существовал хотя бы один торговый маршрут. План Ивана и Панамки очень прост — каждый раз, когда ячейка должна быть превращена из моря в землю, они проверяют, не получится ли так, что после превращения не останется ни одного торгового маршрута. Если хотя бы один маршрут остается, они превращают море в землю на этой ячейке, и переходят к следующей ячейке. Если ни одного маршрута не остается, они не превращают эту ячейку в землю, и переходят к следующей ячейке.

Ваша задача симулировать этот процесс, и определить, сколько же ячеек в конечном итоге будет превращено из моря в землю.