RoAlgo Contest #6 | transformare

The Earth can be viewed as a matrix with $N$ rows and $M$ columns, consisting only of the digits $1$ and $0$, where $1$ represents an island and $0$ represents water. After extensive research, it has been discovered that each island needs at least $K$ neighboring water positions to transform and become water. The neighbors of an island can be in the N, S, E, or W directions. Additionally, islands have a single special direction (NE, SE, SW, or NW) which represents another neighbor for that island. The transformation of an island into water takes one year.

Task

Knowing the islands, the number $K$ for each island, and each special direction:

1. Determine how many islands transform into water after one year.
2. For $Q$ queries of the form $(x, y)$, determine after how many years the island located at $(x, y)$ will become water. If it is not possible for $(x, y)$ to become water, print -1.

Input data

The first line of the input contains $4$ natural numbers, $C$, $N$, $M$, and $P$, in this order, separated by a space. The next $P$ lines each contain four natural numbers $x$, $y$, $K$, and $d$, separated by a space, representing the coordinates of an island, the number of neighboring water positions required for it to transform, and its special direction. For $d = 1$, the direction is NE, for $d = 2$, SE, for $d = 3$, SW, and for $d = 4$, NW. If $C = 2$, then on the next line, the number of queries $Q$ is read, and on the following $Q$ lines, the numbers $x$ and $y$, separated by a space, are read.

Output data

If $C = 1$, then print the number of islands that transform into water after one year. If $C = 2$, then print the answer to each of the $Q$ queries, each on a separate line.

Constraints and clarifications

• $1 \leq N, M \leq 1,000$
• $0 \leq K \leq 5$
• $1 \leq P \leq N \cdot M$
• $1 \leq Q \leq N \cdot M$
• $d \in \{1, 2, 3, 4\}$
• There is a chance that some neighbors are outside the Earth. These will not be considered. For example, an island at position $(1, 2)$ with $K = 5$ cannot become water because the northern neighbor does not exist.
• It is guaranteed that for each of the $Q$ queries, $(x, y)$ represents a position where an island is located.
• The coordinate $x$ represents the row $x$ of the matrix, and the coordinate $y$ represents the column $y$ of the matrix.
• In coordinates where there is no island, there is water.
• To solve this problem in C++, researchers recommend using the following lines of code at the beginning of the main() function:

ios::sync_with_stdio(0);
cin.tie(0);

Example 1

stdin

1 4 5 9
1 1 1 2
1 2 2 3
1 5 2 1
2 2 4 3
3 4 2 1
4 2 3 1
4 3 2 2
4 4 4 4
4 5 0 1

stdout

7

Example 2

stdin

2 4 5 9
1 1 1 2
1 2 2 3
1 5 2 1
2 2 4 3
3 4 2 1
4 2 3 1
4 3 2 2
4 4 4 4
4 5 0 1
5
1 1
1 5
2 2
4 3
4 4

stdout

1
1
1
2
3

Explanation

The image below corresponds to both examples. The numbers on an island represent the value $K$ of the island, the arrows represent the special direction of the island, and if the $K$ value of the island is in red, it means that island is a query from the $Q$ queries.

Let's discuss the island at position $(3, 4)$. It has $K = 2$, so it must have at least 2 water neighbors to transform into water. The special direction of this island is NE (northeast). Thus, its water neighbors are in the N, NE, E, and W directions. Since $4 \geq K = 2$, this island will transform into water.

The islands that transform into water after the first year are: $\{(1,1), (1,2), (1,5), (2,2), (3,4), (4,2), (4,5)\}$.