Кладоискатель

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера N×M. Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных клеток).

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

Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.

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

Первая строка входного файла INPUT.TXT содержит 2 числа N и M, задающие размеры лабиринта (1 ≤ N, M ≤ 100 , N×M ≤ 100). Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ «*» обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В (N+2)-й строке находится число K (1 ≤ K ≤ N×M) – количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа y_i и x_i, означающие, что i-й вход расположен в y_i-й строке и в x_i-м столбце (1 ≤ y_i ≤ N, 1 ≤ x_i ≤ M). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

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

Примеры

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

[Обсуждение] [Все попытки] [Лучшие попытки]