Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Жук

(Время: 2 сек. Память: 16 Мб Сложность: 30%)

Петя нашел в Интернете по адресу http://buglab.ru игру-головоломку "Жук", в которой от участников требуется построить для жука лабиринт таким образом, чтобы жук как можно дольше искал выход.

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

Изучив алгоритм движения жука Петя хочет написать программу, которая по заданному лабиринту определит количество перемещений жука прежде, чем он достигнет выхода. Помогите Пете с реализацией данной программы!

Конструктор лабиринта

- кнопка запуска жука Ходы: 0

Входные данные

Входной файл INPUT.TXT в первой строке содержит разделенные пробелом целые числа N и M - количество строк и столбцов в лабиринте (4 ≤ N, M ≤ 100). Далее следует N строк, содержащих данные лабиринта построчно. Каждая строка содержит M символов - клетки лабиринта текущей строки, где символ "@" обозначает присутствие стены, а символ пробела - пустое пространство. Гарантируется, что граница лабиринта окружена стеной. Предполагается, что жук начинает свое движение из координаты (2, 2) и заканчивает в координате (M-1, N-1), подразумевается, что в этих координатах нет стен. Гарантируется, что если выход из лабиринта существует, то жук сможет выйти из него, сделав не более 107 шагов.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество движений жука, если спасительный маршрут для жука существует, и -1 в противном случае.

Примеры

¹INPUT.TXTOUTPUT.TXT
16 6
@@@@@@
@    @
@    @
@ @ @@
@ @  @
@@@@@@
20
28 30
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@   @    @ @@@@ @  @ @@@@ @@ @
@ @ @@ @  @ @     @ @ @      @
@   @  @ @ @@  @@        @@ @@
@             @           @ @@
@ @  @@ @ @   @@@  @  @   @  @
@     @   @  @    @   @ @@   @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
630
34 4
@@@@
@ @@
@@ @
@@@@
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023
 2023 / 2024
 A. Больше-меньше
 B. Четырехзначный палиндром
 C. Кругляши
 D. Жук

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ICQ: 151483, E-mail: admin@acmp.ru