Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе --> Обход в ширину
    0-1 BFS(3 задач)
---> 7 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 1 2 Отображать по:
#3184
Космические исследования
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отделу космических исследований поступило задание сфотографировать из космоса \(n\) объектов в заданной области. Область имеет форму квадрата размером \(50\times 50\) километров. Если разделить ее на квадраты размером \(1\times 1\) километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером \(k\times k\) километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами \(x\) и \(y\) от \(1\) до \(k\) километров.

С помощью специальных двигателей можно изменять орбиту спутника, что приводит к изменению участка съемки. За один день орбиту спутника можно изменить таким образом, что участок съемки сместится либо на один километр на запад, либо на один километр на восток, либо на один километр на север. Переместить участок съемки на юг невозможно. Непосредственно между перемещениями спутника можно сделать снимок, временем съемки можно пренебречь.

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

Требуется написать программу, которая по заданному расположению объектов и размеру снимка \(k\) определит минимальное время, за которое можно сделать снимки всех объектов заданной области.

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 5\)).

Следующие \(n\) строк содержат по два целых числа: \(x_i\) и \(y_i\) — координаты объектов в заданной области (\(1 \le x_i, y_i \le 50\)).

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

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

Примечание

В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.

Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Правильные решения для тестов, в которых \(k = 1\), будут оцениваться в 30 баллов.

Правильные решения для тестов, в которых \(k \gt 1\) и \(1 \lt n \le 15\), будут оцениваться так же в 30 баллов.

Примеры
Входные данные
4 1
1 1
10 2
1 3
10 4
Выходные данные
30
Входные данные
4 2
1 1
10 2
1 3
10 4
Выходные данные
10
Входные данные
1 1
1 1
Выходные данные
0
Входные данные
3 3
3 3
3 6
6 3
Выходные данные
7
#111475
Обмен королей (O)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Шахматной Стране всегда пользовались популярностью различные спортивные соревнования: ферзебол, рокировочная борьба, эндшпилевые бега. Но наибольшую популярность в этом году получила спортивная игра «обмен королей».

Суть её заключается в следующем. Двух королей (белого и чёрного) ставят на прямоугольное шахматное поле, некоторые клетки которого отмечены как недостижимые. По правилам игры короли делают ходы по очереди (сначала белый, а затем чёрный), не наступая на недостижимые клетки. Игра считается успешно законченной, если черный и белый короли поменялись местами. В соревновании побеждает та пара королей, которая смогла поменяться местами за минимальное количество ходов.

Напомним, что в шахматах король имеет право переместиться из своей клетки в любую из 8 соседних по вертикали, диагонали или горизонтали, при условии, что она не является соседней для другого короля.

Напишите программу, которая по информации о доске найдет минимальное количество ходов, необходимое для успешного окончания игры.

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

В первой строке входных данных даны целые числа N и M (1 ≤ N, M ≤ 8) — размеры доски по вертикали и по горизонтали, соответственно. В следующих N строках даны M символов — состояние доски в начале игры. Символ «.» обозначает пустую клетку, символ «*» — недостижимую клетку, символ «W» — белого короля, «B» — черного короля. Гарантируется, что символы «W» и «B» встречаются на поле ровно по одному разу, и короли не находятся в соседних клетках изначально.

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

В выходной файл необходимо вывести минимальное количество ходов, которое потребуется для того, чтобы белый король поменялся местами с чёрным. В случае, если поменять королей местами невозможно, требуется вывести «Impossible» без кавычек.

Примеры тестов

Входные данные
4 3
*.*
W.B
...
*.*
Выходные данные
8
Входные данные
2 3
W..
..B
Выходные данные
Impossible

Примечание

Последовательность ходов, необходимая для обмена королей в первом тесте, приведена на рисунке:

Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест