BSSPC '22 P3 - Searching for Seats

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 512M

Problem type

You're running late for your favorite club because of hall traffic. Of course it's the computer club! When you finally arrive, the club has already started and you must make the all-important decision of where to sit.

The classroom can be represented by an N \times M grid, with N rows and M columns of seats. Additionally, a person sitting in any of the up to 8 seats surrounding a seat is considered to be sitting next to the person in the middle.

Naturally, you want to sit next to some of your friends, and as it happens, all K students attending that day are your friends!

Given the coordinates (r_i, c_i) of all K of your friends, find the number of possible seats that you can sit in, where you sit next to at least 3 friends.

Note that a seat can only fit one person, either you or one of your friends. Please do not push your friends off of chairs.


1 \le N, M \le 10^3

1 \le K \le N \times M

1 \le r_i \le N

1 \le c_i \le M

Input Specification

The first line of input contains three integers, N, M, and K.

The next K lines contain two integers each, the i^\text{th} containing r_i and c_i.

Output Specification

Output a single integer, the number of seats you can sit in where you are next to at least 3 friends.

Sample Input

3 4 5
1 2
1 4
2 1
3 1
3 3

Sample Output



The grid is shown below:


Your classmates are marked by #, and seats you can sit in that are next to at least 3 friends are marked by x.


There are no comments at the moment.