Official Editorial (C++)

Explanation 1:

We first find the largest one-cow region through floodfills from every non-visited cell.

The largest two-cow region technically takes an optimization to pass in time. We map every cell to its floodfilled component. We then build edges between all adjacent cells of different colors. Finally, instead of doing a floodfill from every differing pair of adjacent colors, we can use the edges between components and add up the sizes for entire regions at once. We fix the first component and iterate over all adjacent ones for this floodfill. The region sizes are determined from the one-cow floodfill from earlier.

The solution uses an iterative approach to floodfill instead of a recursive approach.

Implementation

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

Copy
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;

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

public class Multimoo {
	private int n, cnt, id = 1;
	private Map<Integer, Integer> idToSize = new HashMap<>();
	private Map<Integer, Integer> idToColor = new HashMap<>();
	private Map<Integer, List<Integer>> componentAdj = new HashMap<>();
	private int[][] grid, ids;
	private int[] dirr = {1, 0, -1, 0};

Copy
from collections import defaultdict, deque


def flood_fill(r, c, color, n, grid, ids, id_val, cnt):
	dirr = [1, 0, -1, 0]
	dirc = [0, 1, 0, -1]

	queue = deque([(r, c)])

	while queue: