Школа программиста

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


 

Цивилизация

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

Карта мира в компьютерной игре «Цивилизация» версии 1.0 представляет собой прямоугольник, разбитый на квадратики. Каждый квадратик может иметь один из нескольких возможных рельефов, для простоты ограничимся тремя видами рельефов – поле, лес и вода. Поселенец перемещается по карте, при этом на перемещение в клетку, занятую полем, необходима одна единица времени, на перемещение в лес – две единицы времени, а перемещаться в клетку с водой нельзя.

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

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

Во входном файле INPUT.TXT записаны два натуральных числа N и M, не превосходящие 1000 – размеры карты мира (N - число строк в карте, M – число столбцов). Затем заданы координаты начального положения поселенца y и x, где y – номер строки, x – номер столбца на карте (1 ≤ y ≤ N, 1 ≤ x ≤ M), строки нумеруются сверху вниз, столбцы – слева направо. Затем аналогично задаются координаты клетки, куда необходимо привести поселенца.

Далее идет описание карты мира в виде N строк, каждая из которых содержит M символов. Каждый символ может быть либо «.» (точка), обозначающим поле, либо «W», обозначающим лес, либо «#», обозначающим воду. Гарантируется, что начальная и конечная клетки пути поселенца не являются водой.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14 8 1 1 4 8
....WWWW
.######.
.#..W...
...WWWW.
13
24 7 2 2 3 6
#######
#WW#..#
#WW#..#
#######
-1

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

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



Информация seo на сайте.