Областная олимпиада по информатике, 2009-2010 учебный год


Задача A. Ферзи

Ограничение по времени:
2 sec.
Ограничение по памяти:
64MB

Ферзь – самая сильная шахматная фигура, которая за один ход может перемещаться на любое число полей по вертикали, горизонтали или диагонали (при условии, что на его пути нет фигур). Клетка бьется ферзем, если он может попасть на нее одним ходом. На доске N×N расставлено К ферзей. Посчитайте количество пустых клеток доски, которые не бьются ни одним ферзем.
Формат входного файла
Первая строка входного файла содержит два целых числа N и K (1 ≤ N ≤ 10000, 1 ≤ К ≤ 100000). Каждая из следующих К строк содержит по два числа – номера строк и столбцов, на которых стоит соответствующий ферзь (строки и столбцы нумеруются целыми числами от 1 до N). Позиции всех ферзей различны. Числа в строках разделены пробелами.
Формат выходного файла
Выведите одно целое число – ответ к задаче.
Пример:
Вход:
3 2 
3 2 
2 3
 Ответ:
1

посмотреть в олимпиаде

Комментарий/решение:

  0
2018-10-06 11:33:07.0 #

#include<iostream>

using namespace std;

bool a[10001][10001];

void f(int x,int y,int n)

{

for(int i=1;i<=n;i++)

{

a[x][i]++;

a[i][y]++;

int q=x,w=y;

if((x+i<=n+1 && y+i<=n+1))

{

a[x+i][y+i]++;

if(x!=1 && y!=1)

{

a[x-i][y-i]++;

}

if(y!=1)

a[x+i][y-i]++;

if(x!=1)

a[x-i][y+i]++;

}

}

}

int main()

{

int n,m,cn=0;

cin>>n>>m;

for(int i=1;i<=m;i++)

{

int x,y;

cin>>x>>y;

a[x][y]++;

f(x,y,n);

}

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

if(!a[i][j]) cn++;

}

}

cout<<cn;

}