CCCHK '15 J3 - Queens can't attack me! - DMOJ: Modern Online Judge

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

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

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 \leq N \leq 100, 1 \leq M \leq 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 \leq x, y \leq N)$ .

Output Specification

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

Sample Input 1

Copy

6 1
4 3

Output for Sample Input 1

Copy

Sample Input 2

Copy

6 2
4 3
6 4

Output for Sample Input 2

Copy

Explanation

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

Comments

-15

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

first

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