The forest is represented by a 0,1-matrix. We will call the values 0 and 1 **colors**, **0**
being **white** and **1** **black**. Instead of selecting a tree that has to be enchanted
we select the corresponding element of our matrix. It is simple to divide the matrix into
maximal connected one-colored areas. The spell performs a flood-fill starting at the selected
element – the whole area containing the selected element changes color (from white to black
or vice versa).

Let's construct a graph **G _{m} = (V,E)** where vertices will represent the areas in the
matrix. Two vertices will be connected by an edge iff the corresponding two areas are adjacent
(e.g. one of them contains an element with the coordinates

What will happen with our graph after casting the spell? The selected area will change its color
and merge with all neighboring areas into one larger area. Or, speaking in graph terms, we join
the selected vertex and all its neighbors into one "large" vertex. Its color will be the opposite
of the color of the selected vertex. We may throw away all the loops
(previously edges between the selected vertex and its neighbors).
We will call this operation **a contraction of the vertex v**.
Note that also after any contractions all neighbors of a white vertex are black and vice versa.
Our goal is to create a graph with only one vertex using as few contractions as possible.

Let **G** be an undirected graph. We start by defining some terms:

- We will denote the length of the shortest path between
**u**and**v**as**d(u,v)** - The
*eccentricity*of a vertex**v**is the maximum of the shortest distances from**v**to other vertices in**G**. Formally,**ex(v) = max { d(v,u) | u in G }** - A vertex
**c**is called a*central point*of**G**iff no other vertex in**G**has a smaller eccentricity. Formally,**c**is a central point iff**ex(c) = min { ex(u) | u in G }**. Obviously, at least one vertex in each graph is a central point. There may be more such vertices. - The
*radius***r**of the graph**G**is the minimum of all the eccentricities, or equivalently the eccentricity of a central point.

Lemma 1: After a contraction of a central point **c** the radius **r** of the graph decreases (at
least by 1).

Proof: For each neighborvofcwe haved(v,c) = 1. Consider a vertexu != c, take any shortestu-cpath. It leads through exactly one neighborvofc. Therefored(u,c) = d(u,v) + d(v,c) = d(u,v) + 1. It follows that the eccentricity ofc'after the contraction will be one smaller than the eccentricity ofcbefore the contraction. Letr'be the radius of the contracted graph. We know thatr'<=ex(c')andex(c')<ex(c)=r, q.e.d.

Lemma 2: Let **c** be any central point. After a contraction of any vertex **v in V**
the eccentricity of **c** stays the same or decreases by 1.

Proof: Suppose

v=c. We already proved that after a contraction ofcits eccentricity decreases by one. Now supposev!=c. Proof by contradiction. Clearly the eccentricity ofcmay not increase, therefore suppose it decreases at least by two. For each vertexuwe take an arbitrary shortestc-upathP. As_{u}cis a central point, the length of somePis_{u}r. We will now find a vertexbsuch thatex(b)was less thanrbefore the contraction. This will be a contradiction, because the eccentricity ofcwas the smallest one.We assumed that after the contraction

ex(c)<=r-2. Consider the pathsP. Some of them were already shorter than_{u}r-1before the contraction, we won't be interested in these. At least one of them had lengthr. EachPof length_{u}ris now shorter at least by two. It follows that either thisPpasses through_{u}vor through at least three neighbors ofv. Without loss of generality (why?) we may assume the first case. EachPof length_{u}r-1is now shorter at least by one. It follows that either thisPpasses through_{u}vor through at least two its neighbors.Let

bbe the first vertex on some shortestc-vpath (a neighbor ofc). We will show that (in the graph before the contraction)ex(b)<r. Letube an arbitrary vertex. We consider the following cases:

- Case 1.
d(c,u)<=r-2.

Thend(b,u)<=d(b,c)+d(c,u)=1+(r-2)=r-1.- Case 2.
d(c,u)=r-1andPpasses through two neighbors_{u}v._{1},v_{2}

We may assume thatd(v, otherwise there is a shortest_{1},v_{2})=1c-upath passing throughv, we will handle this vertex in case 3. We know that the shortestb-upath is not longer than the shortestb-v-vpath. We also know that_{2}-ud(c,v)<=d(c,v, therefore_{1})+1d(c,v)-1<=d(c,v._{1})

We have:d(b,u) <= d(b,v)+d(v,v. Or the same in words: there is a_{2})+d(v_{2},u) = (d(c,v)-1)+1+d(v_{2},u) <= d(c,v_{1})+d(v_{1},v_{2})+d(v_{2},u) = d(c,u) = r-1b-upath (leading throughvandv) that is at most as long as the shortest_{2}c-upath (leading throughvand_{1}v). The following image may help if you have problems understanding this step of our proof._{2}

- Case 3.
r-1<=d(c,u)<=randPpasses through_{u}v.

We know thatd(c,u)=d(c,v)+d(v,u). Butd(b,v)=d(c,v)-1and thusd(b,u)<=d(b,v)+d(v,u)=d(c,u)-1<=r-1.We have reached a contradiction –

ex(b)<rbut thencis not a central point. Therefore our assumption was wrong and the lemma is proved.

Theorem: The least number of contractions needed to contract the whole graph into a single vertex
is **r**.

Proof: Follows from the above lemmas. Letcbe any central point. After arbitraryr-1contractionsex(c)>0and therefore the graph has at least two vertices. On the other handrcontractions suffice – e.g. always contract the vertexc.

The algorithm is now pretty straightforward – we have to transform the given matrix to a
graph and find its central point. The transformation can be easily done in **O(RC)** time.
Then we will compute the eccentricity of each vertex by running a BFS (breadth first search)
from each vertex. The time complexity of this part is **O(N(M+N))**, where **N** is the number
of vertices and **M** is the number of edges of the graph. Note that the graph is planar,
therefore **M=O(N)**. The resulting time complexity is therefore **O(RC+N ^{2})**.
(In the worst case this is