Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Кладоискатель

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера NM (1NM100 , NM100). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).
 
В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть K входов, из которых Вася может начать свой путь.
 
Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.
 
Входные данные
Первая строка содержит 2 числа N и M, задающие размеры лабиринта. Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
 
В (N+2)-й строке находится число K (1<=K<= NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1xiN1yiM). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
 
Выходные данные
Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.

Ввод Вывод
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
 
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
-1


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: