Задача Queens
Ферзь – шахова фігура, яка ходить по горизонталі, вертикалі або діагоналі на довільну кількість клітинок. Клітинка безпечна, якщо на ній не стоїть ферзь і коли жоден ферзь не може в ній опинитись за один хід. На квадратній шахівниці розміщені ферзі. Порахуйте на ній кількість безпечних клітинок.
Технічні умови. Програма Queens читає з клавіатури через пропуск два числа – розмір шахівниці N та кількість ферзів K (1≤N≤10000, 1≤K≤100000). Далі програма читає K рядків по два розділених пропуском натуральних числа i та j, не більших N – номери рядків і стовпчиків, на яких стоїть відповідний ферзь. Рядки і стовпчики нумеруються від 1 до N цілими числами. Жодні два ферзі не стоять на одній клітинці. Програма виводить на екран єдине число – кількість безпечних клітинок.
Приклад
Введення
3 2
3 2
2 3
Виведення
1
© LIKT 1998-2018