ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Крепкий орешек

Ограничение времени: 5.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
Джон попал в город, представляющий собой сетку из квадратных клеток размером N × M. В некоторых клетках находятся здания, некоторые клетки пустые. Джон находится в клетке (x0, y0). Он может двигаться из одной клетки в соседнюю по горизонтали, по вертикали и по диагонали со скоростью V. Ему сообщают по рации список точек, в которых заложены бомбы. Джон должен обезвредить их в том же порядке, в каком они перечислены, или умереть. Если он не может добраться до какой-либо бомбы, то он переходит к следующей. Все бомбы заложены вне зданий.
За какое минимальное время Джон сможет закончить свою работу, если считать, что бомбы он обезвреживает мгновенно?

Исходные данные

В первой строке через пробел записаны числа N, M, K (количество бомб), и V, удовлетворяющие ограничениям 1 ≤ N, M ≤ 75; 1 ≤ K ≤ 1000; 0.01 < V < 10.00. Далее следует карта города — M строк по N символов в каждой. Символ '.' обозначает незастроенный квартал, '#' обозначает здание. После этого идёт строка, содержащая координаты (x0, y0). Ввод завершается K строками с координатами бомб в порядке их прохождения Джоном.

Результат

Необходимо вывести единственное число — минимальное время. Время необходимо указать с точностью до двух знаков после десятичной точки.

Пример

исходные данныерезультат
4 3 3 1.23
....
##..
....
1 1
1 3
4 1
4 3
8.66
Автор задачи: Павел Атнашев
Источник задачи: Open collegiate programming contest for student teams, Ural State University, March 15, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1254. Крепкий орешек