For each red square, consider the difference of the number of connected component by repainting it green.

Fix a red square \((i,j)\). Suppose that there are \(x\) connected components that contain a green square adjacent to the square \((i,j)\).

By repainting \((i,j)\) green, all the green squares adjacent to \((i,j)\) becomes connected with \((i,j)\), so the number of connected components containing \((i,j)\) or a square adjacent to \((i,j)\) becomes \(x\) to \(1\). The number of components elsewhere does not change, so the number of connected component decreases by \((x-1)\). (For \(x=0\), it decreases by \(-1\); in other words, it increases by one.)

Therefore, one can precompute the connected component that each vertex belong in the original graph using BFS (Breadth-First Search), DFS (Depth-First Search), or DSU (Disjoint Set Union) to solve the original problem.