Assume wlog the blue "army" "wins" in the end, and consider one of the initial contiguous blue region which survives until the end. Assume that at any point of the "expansion" of this region, it meets a red "soldier". At each turn, the "division" (i.e the evolution of this initial red soldier/connected red region) created by this red soldier keeps attacking at least one blue soldier, and creates at least one more soldier contiguous to the new blue division. So in each turn there must always be such a situation with a red attacking a blue, which means the blue army can't win. Therefore, at each moment of time, each blue soldier either borders with other blue soldiers or against yellow soldiers. Now, consider a blue soldier of the above said original region, and call him the "special commander" which gives rise to a blue "special division", which also expands into regular blue territory. By what we said before, this special division can't have any enemy since it can never meet a red soldier, so it will expand indefinitely. Finally, assuming the armies were fighting house by house in New York, we can use the Manhattan distance to say that the special division will reach every house in at most $2n-2$ turns, because the special commander is distant at most $(n-1)+(n-1)$ from every other house.

Oops I forgot to post Replace red, yellow, blue with elephant, mouse and snake, respectively. Rules remain the same. WLOG in the end, all squares are occupied by elephants. Call a component of elephants a set of squares of elephants such that one can go from two elephant squares in the same component using elephant squares sharing an edge. The key structural insight is that there exists an elephant component that is never adjacent to a mouse square in the entire process. This clearly finishes the problem, because if I have a starting square $S$, on the $j$th move, all squares with distance at most $j$ from $S$ will be covered with elephants. Since all squares are within $2n-2$ squares from any starting square, plugging $j=2n-2$ implies the problem. It remains to prove the key structural claim. Consider a mouse square adjacent to a component of elephant squares, and call its component $M$. Observe as long as the component of elephant squares $C$ is nonempty, the component of mouse squares $M$ can turn squares in $C$ into mouse squares because $M$ is adjacent to $C$. In other words, squares in $C$ either disappear due to $M$ or not due to $M$. It either gets empty or has squares disappearing at every turn. Therefore, if all components of elephants become adjacent to one mouse square, the mouse squares can either conquer elephant squares or there would be none left, contradicting our assumption that in the end, all squares will be conquered by elephants.

I'm not quite convinced by the above proofs, as the logics don't seem to be clear enough. Instead I have the following argument. We assume without loss of generality that all squares turn red in the end. For each square $X$, we define $s(X)$ as the smallest integer $k$ such that $X$ remains red from round $k$ until the end. Claim 1: for each square $X$, either $s(X) = 0$ or there exists a square $Y$ next to $X$ with $s(Y) \leq s(X) - 1$. Proof: Suppose $s(X) = k > 0$. Then $X$ turns from blue to red at round $k$, which means that at round $k - 1$ there is a red square $Y$ next to $X$. The square $Y$ cannot change color after round $k - 1$: if it changed to yellow at some round $m \geq k$, then $X$ would also change to yellow at round $m + 1$, contradicting the defintion of $s(X)$. Therefore $Y$ remains red after round $k - 1$, i.e. $s(Y) \leq k - 1$. Claim 2: if two squares $X, Y$ are next to each other, then $|s(X) - s(Y)| \leq 1$. Proof: Write $k = s(X)$ and suppose $s(Y) \leq k - 2$. The square $X$ must be blue at round $k - 1$, and hence must be either blue or yellow at round $k - 2$. By assumption, the square $Y$ is already red at round $k - 2$. If $X$ is blue at round $k - 2$, then it would turn into red at round $k - 1$, contradiction. If $X$ is yellow at round $k - 2$, then $Y$ would turn into yellow at round $k - 1$, contradicting the assumption $s(Y) \leq k - 2$. Thus we have contradiction in either case, proving the claim. The original question is then a consequence of the follow simple result: Fill each squre in an $n \times n$ grid with a nonnegative integer, such that - if a square has $k > 0$ in it, then one of its neighbor has $k - 1$; - if two squares are next to each other, then their numbers differ at most by $1$. Then the largest number in the grid is at most $2n - 2$. Proof: the first requirement tells us that there is at least one square with $0$ in it; the second requirement tells us that any two squares have numbers that differ at most by their Manhattan distance.

The crux of this problem is the following claim. Claim: There exists a cell that never changes color. Proof: By the condition, the color of every cell must eventually become constant. Consider a cell $\mathcal{A}$ that first becomes a constant color, and assume WLOG that the color is red. Assume FTSOC that $\mathcal{A}$ was not always red. Then, it must have a red neighbor $\mathcal{B}$ before it changed to red. However, $\mathcal{B}$ cannot become yellow, or $\mathcal{A}$ would become yellow, a contradiction. Thus, the color of $\mathcal{B}$ becomes constant before $\mathcal{A}$ does, contradicting the assumption that $\mathcal{A}$ is the first square to become constant. $\square$ Thus, there exists a cell $\mathcal{A}$ that never changes color. Consider the graph with vertices representing cells and edges connecting orthogonally adjacent cells. Then, the cells adjacent to $\mathcal{A}$ must be red or blue, so they must become red after $1$ round. Similarly, the cells of distance $2$ away from $\mathcal{A}$ must be red or blue after $1$ round, so they must become red after $2$ rounds. We can continue this argument to show that all cells a distance $k$ away from $\mathcal{A}$ must become red after $k$ rounds. Since all cells are of distance at most $2n-2$ from $\mathcal{A}$, they must all become red in $2n-2$ rounds. $\square$

Perhaps my first combinatorics post Through the solution two cells are neighbor if they share a common edge. we say a cell is $Unicorn$ if it never changes color from the start until the grid is monochromatic. Claim $:$ If grid becomes monochromatic then it had at least one $Unicorn$ cell in the initial grid.

so now we may Assume our initial grid has a $Unicorn$ cell. for a group of cells like $S$, Let $f(S)$ be all cells which are not in $S$ and are neighbor to at least one cell in $S$. Let $U$ be the $Unicorn$ cell in the initial grid. $f^m(U)$ is $f(f(...f(U)...))$. Claim $:$ After the $k$-th round all the $U,f(U),f^2(U),...,f^k(U)$ are $yellow$.

since two cells in an $n \times n$ grid have at most $2n-2$ distance then $U\cup f(U)\cup ... \cup f^{2n-2}(U)$ will cover all the grid and so the grid has became monochromatic no later than the end of the $(2n-2)$-th round.

here is a way to visualize this problem: paste the following code into https://lazyslug.com/ x=0, y=0, rule=a ! @RULE a @TABLE n_states:4 neighborhood:vonNeumann symmetries:permute var a1 = {0,1,2,3} var a2 = {0,1,2,3} var a3 = {0,1,2,3} var a4 = {0,1,2,3} 0, a1,a2,a3,a4, 0 1, 2,a1,a2,a3, 2 1, a1,a2,a3,a4, 1 2, 3,a1,a2,a3, 3 2, a1,a2,a3,a4, 2 3, 1,a1,a2,a3, 1 3, a1,a2,a3,a4, 3 @COLORS 0 0 0 0 1 255 0 0 2 255 255 0 3 0 0 255