Задача №1329. Кладоискатель
Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\)). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).
В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть \(K\) входов, из которых Вася может начать свой путь.
Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.
Первая строка содержит 2 числа \(N\) и \(M\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.
5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5
1
3 3 010 1*1 010 4 1 1 1 3 3 1 3 3
-1