Ферзи, кони и пешки
Ферзи, кони и пешки
Вы все вероятно знакомы с знаменитой задачей о 8-ми ферзях, в которой Вас просят разместить 8 ферзей на шахматной доске так, что никакие два не нападают друг на друга. В этой задаче вам заданы расположенные в некоторых местах ферзи, кони и пешки и вам необходимо выяснить, сколько свободных клеток на доске не находятся под атакой как ферзя, так и коня (или обеих). Мы будем называть такие клетки "безопасными" клетками. Здесь пешки будут служить лишь в качестве блокираторов и не имеют возможности нападения на другие клетки. Доска, изображённая на рисунке ниже, имеет 6 безопасных клеток (затенённые клетки находятся в безопасности).
Напомним, что конь может перейти с текущей позиции на любую незанятую клетку, которая находится в противоположном углу прямоугольника 2х3, ферзь движется к любой клетки, которая видна в любом из восьми горизонтальных, вертикальных и диагональных направлений от текущего положения. Обратите внимание, что перемещение ферзя может быть заблокировано другой фигурой, в то время как перемещение коня - не может.
Giriş verilənləri
Вам будет задано несколько тестов. Каждый тест состоит из 4-х строк. Первая строка будет содержать два целых числа n и m, указывающие размеры доски, задавая количество строк и столбцов соответственно. Ни одно число не будет превышать 1000. Каждая из последующих трёх строк будет имеет вид
k r_1 c_1 r_2 c_2 ... r_k c_k
с указанием количества и расположения ферзей, коней и пешек, соответственно. Нумерация строк и столбцов начинается с единицы. Количество каждой из фигур будет не более 100. Значения n = m = 0 указывают на окончание входных данных.
Çıxış verilənləri
Для каждого теста необходимо вывести одну строку вида
Board b has s safe squares.
где b - это номер теста (начиная с единицы), а также вы указываете правильное значение для s.
Nümunə
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
Board 1 has 6 safe squares. Board 2 has 0 safe squares. Board 3 has 996998 safe squares.