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

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem type

Consider a square chessboard with N \times N cells and 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 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 cells that cannot be reached by the queen.

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 and M (1 \le N \le 100, 1 \le M \le 10). Following are M lines. Each line contains two integers x and y, representing the location of a queen, i.e., the queen is at xth row and yth column (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



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


There are no comments at the moment.