Official Analysis (Java)

Explanation

Let's view the grid as a graph, where each cell is a vertex, and each border between two grids that does not contain a road is an edge. For two cows to need to cross a road to reach each other, they must belong to two different connected components in the graph.

We perform floodfill to find each connected component and the number of cows within it. For a pair of connected components, each possible pair of cows between these connected components must cross a road to reach the other. Thus, the answer is the sum of pairwise products between the number of cows in each component.

Naively implementing this solution takes $\mathcal{O}(N^4)$ time, as we are computing pairwise products with up to $\mathcal{O}(N^2)$ components. This can be optimized to $\mathcal{O}(N^2)$, as described below:

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
from typing import List, Tuple


def neighbors(r: int, c: int) -> List[Tuple[int, int]]:
	""":return: the 4 cardinal neighbors of a position"""
	return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]


with open("countcross.in") as read:
	side_len, cow_num, road_num = [int(i) for i in read.readline().split()]