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

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


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 49%)

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера 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-й строке содержатся числа yi и xi, означающие, что i-й вход расположен в yi-й строке и в xi-м столбце (1 ≤ yi ≤ N, 1 ≤ xi ≤ M). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
1
23 3
010
1*1
010
4
1 1
1 3
3 1
3 3
-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 - 2023, E-mail: admin@acmp.ru



листовая панель из рустованного хдф