Задача Queens

Ферзь – шахова фігура, яка ходить по горизонталі, вертикалі або діагоналі на довільну кількість клітинок. Клітинка безпечна, якщо на ній не стоїть ферзь і коли жоден ферзь не може в ній опинитись за один хід. На квадратній шахівниці розміщені ферзі. Порахуйте на ній кількість безпечних клітинок.

Технічні умови. Програма Queens читає з клавіатури через пропуск два числа – розмір шахівниці N та кількість ферзів K (1N10000, 1K100000). Далі програма читає K рядків по два розділених пропуском натуральних числа i та j, не більших N – номери рядків і стовпчиків, на яких стоїть відповідний ферзь. Рядки і стовпчики нумеруються від 1 до N цілими числами. Жодні два ферзі не стоять на одній клітинці. Програма виводить на екран єдине число – кількість безпечних клітинок.

Приклад

Введення

3 2

3 2

2 3

Виведення

1

© LIKT 1998-2018