Explanation

Our approach is to perform 2D Prefix Sums, where our prefix sums array calculates how many connected components there are from (0, 0) to (x, y). However, it is not clear what the transition function is. For example, if our grid looks like this,

01
11

$\texttt{prefix}_{0, 1} = 1$ as there is one connected component in the first row, and $\texttt{prefix}_{1, 0} = 1$ as there is one connected component in the first column. However, $\texttt{prefix}_{1, 1} = 1$ also as these two connected components get merged.

The key to finding the transition function is the line "for every pair of two blue square $a$ and $b$, there is at most one path that starts from $a$, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches $b$, without traversing the same square more than once."

This means that if two separate connected regions are joined at one point, they cannot be joined anywhere else. For example, below, two separate connected components (A and B) are joined at the bottom-right corner (*), so they cannot touch anywhere else.

01101     0AA0A
00101     00A0A
00111     00AAA
10001     B000A
11111     BBBB*

With this in mind, we can do casework. Let's say we're looking for $\texttt{prefix[i][j]}$.

Case 1: $\texttt{grid}_{i, j} = \texttt{grid}_{i - 1, j} = \texttt{grid}_{i, j - 1} = 1$

? 1
1 1

We name $\texttt{grid}_{i - 1, j}$ $A$ and $\texttt{grid}_{i, j - 1}$ $B$.

? A
B 1

Before we added $\texttt{grid}_{i, j}$, $A$ and $B$ must have been part of separate connected components since if otherwise, they must be connected at another location, which violates the problem statement. Therefore, we have merged two connected components into one. In this case, we have, $\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1} - 1$.

Case 2: $\texttt{grid}_{i, j} = 1$, $\texttt{grid}_{i - 1, j} = \texttt{grid}_{i, j - 1} = 0$

? 0
0 1

We have added a new connected component! In this case, we have, $\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1} + 1$.

Case 3: All remaining cases where $\texttt{grid}_{i, j} = 1$

? 1
0 1

Or,

? 0
1 1

We have added on to a previous connected component, so we have, $\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1}$.

Case 4: $\texttt{grid}_{i, j} = 0$ No new connected component can be made by introducing $\texttt{grid}_{i, j}$, and no two connected components can be merged. Therefore, in this case, we simply have, $\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1}$

At this point, we are more than halfway done! However, with this, we can only calculate the change in number of connected components in a certain range. We still need to find how many connected components we start with!

To do this, we calculate how many connected components there are in the top row and left-most column of the range we are searching for. We can use the similar idea, once again using prefix sums.

See the implementation for more details.

Implementation

Time Complexity: $\mathcal{O}(NM + q)$

Since we are performing 2D prefix sums, for convenience, the grid is translated 1 unit right and down. The extra row above and column to the left will be filled with 0's.

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_SIZE = 2e3;

int main() {
	int n, m, q;
	cin >> n >> m >> q;

	/*

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int rowNum = Integer.parseInt(initial.nextToken());
		int colNum = Integer.parseInt(initial.nextToken());
		int queryNum = Integer.parseInt(initial.nextToken());

Copy
MAX_SIZE = 2000

n, m, q = map(int, input().split())

grid = [[False] * (MAX_SIZE + 1) for _ in range(MAX_SIZE + 1)]

# Read the grid
for i in range(1, n + 1):
	row = input()
	for j in range(1, m + 1):