УЧЕБНО - ТРЕНИРОВОЧНЫЕ СБОРЫ К IOI 2003 ДЕНЬ №9 Копперфильд
Входной файл: input.txt Выходной файл: output.txt Время на тест: 1 секунда Тесты к задаче:Скачать
Каждый год известный иллюзионист Копперфильд проводит копперфильдовскую лотерею. Победитель лотереи получает право сыграть с Копперфильдом в игру в его замке, результат которой определяет выигрыш победителя.
Замок состоит из M*N красных и зеленых квадратных комнат, которые располагаются в шахматном порядке. В некоторых комнатах замка включен свет. Победитель лотереи (игрок) первоначально выбирает любую комнату цвета, который укажет Копперфильд, и в которой горит свет. В каждой комнате лежит чек на $1000, и игрок, проходя через комнату, забирает чек себе. Чтобы ограничить передвижения игрока, Копперфильд выключает свет в некоторых комнатах, после чего игрок переходит в одну из соседних комнат, в которой еще горит свет. Игра заканчивается, когда игрок оказывается в единственной светлой комнате. Тогда игрок выигрывает ту сумму денег, которую он собрал, проходя через комнаты замка. Если же в процессе игры Копперфильд выключит свет в комнате, в которой находится игрок, игрок получает все M*N*1000 долларов.
Копперфильд действует так, чтобы даже при наиболее неблагоприятных для Копперфильда действиях игрока, тот собрал как можно меньше чеков. Определить гарантированный выигрыш игрока.
Пояснения.
В начале игры Копперфильд выбирает цвет комнаты (либо красный, либо зеленый), а игрок занимает любую комнату указанного цвета, в которой горит свет, причем Копперфильд не знает, какую именно. Игра происходит по шагам, причем и Копперфильд и игрок обязаны делать свои ходы. На каждом шаге сначала Копперфильд выключает свет в произвольных комнатах по его выбору, затем игрок переходит в одну из соседних четырех комнат, в которой еще горит свет. Игра заканчивается при наступлении одной из следующих трех ситуаций:
После хода Копперфильда игрок оказывается в единственной освещенной комнате в замке. В этом случае игрок забирает себе все чеки, собранные в комнатах, через которые он проходил на пути к последней комнате;
Копперфильд выключает свет в комнате, в которой в текущий момент времени находится игрок. В этом случае Копперфильд проигрывает все чеки, разложенные во всех комнатах замка;
После хода Копперфильда осталось более одной освещенной комнаты, но игрок не может никуда переместиться, так как во всех соседних комнатах свет выключен. В этом случае Копперфильд также проигрывает все чеки, разложенные во всех комнатах замка.
Входные данные
Первыми задаются размеры замка M и N (4 < N, M < 100). Затем, начиная с новой строки, задается план замка. План замка состоит из M строк текста по N символов в каждой строке. Символ "0" означает, что свет в текущей комнате выключен, а символ "1" - включен. Все освещенные комнаты замка связаны друг с другом, то есть из одной освещенной комнаты замка всегда можно пройти в любую другую освещенную комнату, проходя только через освещенные комнаты. В замке в начальный момент игры имеется не более чем 2000 освещенных комнат.
Выходные данные
Напечатайте минимальную сумму денег (в тысячах долларов), которую придется заплатить иллюзионисту при самых худших для него действиях игрока, и координаты комнаты, в которой при этом может оказаться игрок. Левый верхний угол карты имеет координаты (0, 0).
