CCCHK '15 J3 - Queens can't attack me! - Olympiads Online Judge

CCCHK '15 J3 - Queens can't attack me!

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 256M

Problem type

Consider a square chessboard with $N \times N$ ~N \times N~ cells and $M$ ~M~ queens on the chessboard (Note: there are no other chess pieces besides the queens).

A queen can move vertically, horizontally or diagonally. As an example, consider the square chessboard with $6 \times 6$ ~6 \times 6~ cells with one queen (denoted by the ♕ notation) in Figure 1 below. The cells that can be reached by the queen are marked with the ◯ notation. There are $16$ ~16~ cells that cannot be reached by the queen.

$\text{[math]}$

Your task is to calculate the number of cells that are NOT reachable by any queens.

Input Specification

The first line contains two integers, $N$ ~N~ and $M$ ~M~ $(1 \le N \le 100, 1 \le M \le 10)$ ~(1 \le N \le 100, 1 \le M \le 10)~. Following are $M$ ~M~ lines. Each line contains two integers $x$ ~x~ and $y$ ~y~, representing the location of a queen, i.e., the queen is at $x$ ~x~th row and $y$ ~y~th column $(1 \le x, y \le N)$ ~(1 \le x, y \le N)~.

Output Specification

The number of cells that are not reachable by any queens.

Sample Input 1

6 1
4 3

Output for Sample Input 1

Sample Input 2

6 2
4 3
6 4

Output for Sample Input 2

Explanation

Figure 1 and Figure 2 correspond to Sample 1 and Sample 2, respectively.

Comments

-5

EthFng64 commented on Sept. 12, 2024, 10:48 p.m.

first

This comment is hidden due to too much negative feedback. Show it anyway.