Ладья – это шахматная фигура, и позиция каждой ладьи представлена парой (горизонталь, вертикаль), где горизонтали и вертикали пронумерованы от 0 до n – 1.
Ладьи могут атаковать фигуры, стоящие на одной с ними горизонтали или вертикали.
Цель этой задачи – определить набор
безопасных полей на шахматной доске, где ни одна ладья не сможет атаковать их.
Входные данные
- 1 строка содержит два числа:
N - размер доски ( 4 <= N <= 1000000);K - количество расставленныых ладьей ( 0 <= Kw <= 2N );
- следующие K строк содержат позиции расставленных ладьей
Гарантируется, что позиции всех фигур находятся внутри доски и различны.
Выходные данные
Одно число - количество безопасных полей для размещения белого короля
Пример входных данных и расстановки фигур
| Входные данные |
Выходные данные |
Начальная расстановка фигур |
Возможные поля для короля |
8 7 3
0 6
1 5
1 7
2 6
3 3
4 2
5 5
1 6
3 2
6 5
|
41 |
 |
 |
| Некоторые ожидаемые результаты |
Параметры задания
(Размер, позиции белых ладей, позиции черных ладей) |
Ожидаемый результат |
22
(11, 7), (2, 4), (15, 7)
(10, 20), (18, 12) |
397 |
9
(5, 5)
(2, 5), (1, 3) |
52 |
4
(2, 2)
(2, 1) |
10 |
7
(2, 2)
(2, 1), (6, 4), (6, 3) |
22 |