Todd has a grid sheet of paper measuring N by M units and plans to draw squares on it. Each cell in the grid contains an integer X, which represents the center of a square with dimensions (2X - 1) by (2X - 1). Given this grid, Todd wants to know how many squares enclose specific cells. You will be asked Q queries, each with two numbers A and B. Your task is to determine how many of Todd's squares enclose the cell (A, B).
Note: Todd's squares can intersect and form additional shapes, but you only need to consider the original squares he draws, not any new shapes formed by intersections. Even if one square entirely overlaps another, both should be considered separately. The coordinates (A, B) are 0-based. grid[i][j] will contain integer values such that Todd's squares are always contained inside the grid.
Input Format:
The first line contains three integers N, denoting the number of rows in the grid, M, the number of columns in the grid, and Q, the number of queries. The next N lines each contain M integers, representing the grid. The next Q lines each contain two integers: A and B, representing the cell coordinates for the queries.
Output Format:
For each query, print a single integer representing the number of squares that enclose the given cell (A, B).
Constraints:
1 <= N, M <= 10^3
0 <= grid[i][j] <= min(N/2, M/2)
1 <= Q <= 10^5
0 <= A <= N-1
0 <= B <= M-1
Sample Testcase 1:
Input:
5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 2 0
0 1 0 0 0
2 2
Output:
2
Explanation:
Todd's art will look like this: For the query (2, 2), the number of squares enclosing the point is 2 — the red square and the green square.
Sample Testcase 2:
Input:
3 3 2
0 1 0
0 2 1
0 0 0
0 1
1 1
Output:
2
1
Explanation:
Todd's art will look like this: The first query (0, 1) is enclosed by 2 squares, and the second query (1, 1) is enclosed by 1 square.
Asked in: AMAZON_HACKON
Image of the Question
All Testcases Passed ✔
