eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ферзи, кони и пешки

Ферзи, кони и пешки

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Вы все вероятно знакомы с знаменитой задачей о 8-ми ферзях, в которой Вас просят разместить 8 ферзей на шахматной доске так, что никакие два не нападают друг на друга. В этой задаче вам заданы расположенные в некоторых местах ферзи, кони и пешки и вам необходимо выяснить, сколько свободных клеток на доске не находятся под атакой как ферзя, так и коня (или обеих). Мы будем называть такие клетки "безопасными" клетками. Здесь пешки будут служить лишь в качестве блокираторов и не имеют возможности нападения на другие клетки. Доска, изображённая на рисунке ниже, имеет 6 безопасных клеток (затенённые клетки находятся в безопасности).

Напомним, что конь может перейти с текущей позиции на любую незанятую клетку, которая находится в противоположном углу прямоугольника 2х3, ферзь движется к любой клетки, которая видна в любом из восьми горизонтальных, вертикальных и диагональных направлений от текущего положения. Обратите внимание, что перемещение ферзя может быть заблокировано другой фигурой, в то время как перемещение коня - не может.

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

Вам будет задано несколько тестов. Каждый тест состоит из 4-х строк. Первая строка будет содержать два целых числа n и m, указывающие размеры доски, задавая количество строк и столбцов соответственно. Ни одно число не будет превышать 1000. Каждая из последующих трёх строк будет имеет вид

k r_1 c_1 r_2 c_2 ... r_k c_k

с указанием количества и расположения ферзей, коней и пешек, соответственно. Нумерация строк и столбцов начинается с единицы. Количество каждой из фигур будет не более 100. Значения n = m = 0 указывают на окончание входных данных.

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

Для каждого теста необходимо вывести одну строку вида

Board b has s safe squares.

где b - это номер теста (начиная с единицы), а также вы указываете правильное значение для s.

Пример

Входные данные #1
4 4
2 1 4 2 4
1 1 2
1 2 3
2 3
1 1 2
1 1 1
0
1000 1000
1 3 3
0
0
0 0
Выходные данные #1
Board 1 has 6 safe squares.
Board 2 has 0 safe squares.
Board 3 has 996998 safe squares.