P6405 [COCI 2014/2015 #2] ŠUMA

A forest can be modeled as an $n \times n$ matrix, where each element describes the height of a tree. Mirko measured how many meters each tree grows in one year. **Note: if a tree grows $5$ meters in one year, then it grows $2.5$ meters in half a year.** Mirko wants to know: given the current height and growth rate of every tree in the forest, if these trees continue to grow at their current rates, what is the maximum possible number of trees in a connected group whose heights are all equal. Two trees, or a group of trees, are considered connected as follows: - If two trees share a common edge in the matrix, then they are **adjacent**. - If there is a sequence of adjacent trees from the first tree to the second tree, then the two trees are **connected**. - If every pair of trees in the group is connected, then the group of trees is **connected**.

The first line contains a single integer $n$. The next $n$ lines each contain $n$ integers. The number in row $i$ and column $j$ is $h_{i,j}$, representing the initial height of the tree at position $(i, j)$, in meters. The next $n$ lines each contain $n$ integers. The number in row $i$ and column $j$ is $v_{i,j}$, representing the growth rate of the tree at position $(i, j)$, in meters. **Because the input is large, please use a faster input method.**

Output a single line containing one integer, which is the answer.

#### Explanation of Sample 2 After $8$ months, the heights of the trees at $(0,0), (0,1), (1,0)$ will become $\dfrac{13}{3}$ meters. These $3$ trees form a connected group, so the output should be `3`. #### Constraints - For $30\%$ of the testdata, $1 \le n \le 70$. - For $100\%$ of the testdata, $1 \le n \le 700$. For all valid $h_{i,j}$ and $v_{i,j}$, $1 \le h_{i,j}, v_{i,j} \le 10^6$. #### Note **This problem is translated from [COCI2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST #2](https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf) _T5 ŠUMA_.** Translated by ChatGPT 5