codeforces#P2068G. A Very Long Hike
A Very Long Hike
Description
You are planning a hike in the Peneda-Gerês National Park in the north of Portugal. The park takes its name from two of its highest peaks: Peneda (1340 m) and Gerês (1545 m).
For this problem, the park is modelled as an infinite plane, where each position $(x, y)$, with $x, y$ being integers, has a specific altitude. The altitudes are defined by an $n \times n$ matrix $h$, which repeats periodically across the plane. Specifically, for any integers $a, b$ and $0 \leq x, y < n$, the altitude at $(x + an, y + bn)$ is $h[x][y]$.
When you are at position $(x, y)$, you can move to any of the four adjacent positions: $(x, y+1)$, $(x+1, y)$, $(x, y-1)$, or $(x-1, y)$. The time required to move between two adjacent positions is $1 + \lvert \text{alt}_1 - \text{alt}_2 \rvert$, where $\text{alt}_1$ and $\text{alt}_2$ are the altitudes of the current and destination positions, respectively.
Initially, your position is $(0, 0)$. Compute the number of distinct positions you can reach within $10^{20}$ seconds. Your answer will be considered correct if its relative error is less than $10^{-6}$.
The first line contains an integer $n$ ($2\le n\le 20$)—the size of the matrix describing the altitudes.
The following $n$ lines contain $n$ integers each. The $(j+1)$-th number on the $(i+1)$-th of these lines is $h[i][j]$ ($0\le h[i][j] \le 1545$)—the altitude of the position $(i, j)$.
Print the number of distinct positions you can reach within $10^{20}$ seconds. Your answer will be considered correct if its relative error is less than $10^{-6}$.
Input
The first line contains an integer $n$ ($2\le n\le 20$)—the size of the matrix describing the altitudes.
The following $n$ lines contain $n$ integers each. The $(j+1)$-th number on the $(i+1)$-th of these lines is $h[i][j]$ ($0\le h[i][j] \le 1545$)—the altitude of the position $(i, j)$.
Output
Print the number of distinct positions you can reach within $10^{20}$ seconds. Your answer will be considered correct if its relative error is less than $10^{-6}$.
2
3 3
3 3
3
0 0 0
0 1545 0
0 0 0
4
0 1 2 3
5 6 7 4
10 11 8 9
15 12 13 14
2e+40
2e+40
1.524886878e+39
Note
In the first sample, every position of the Peneda-Gerês National Park has an altitude of $3$. Therefore, the time required to move between two adjacent positions is always equal to $1$ second.
In this case, one can show that a position $(x, y)$ is reachable within $10^{20}$ seconds if and only if $|x|+|y| \le 10^{20}$. One can compute that there exist $20\,000\,000\,000\,000\,000\,000\,200\,000\,000\,000\,000\,000\,001$ reachable positions and this number is approximated by $2\cdot 10^{40}$ with a relative error smaller than $10^{-6}$. The sample output shows $2\cdot 10^{40}$ as correct answer, but also the exact number of reachable positions would be a correct answer.
In the second sample, every position $(x, y)$ of the Peneda-Gerês National Park with $x-1$ and $y-1$ divisible by $3$ has an altitude of $1545$, while all the other positions have an altitude of $0$. For example, the time required to move between $(4, 10)$ and $(4, 9)$ is $1546$, while the time required to move between $(3, 2)$ and $(4, 2)$ is $1$.
The positions reachable in $2$ seconds are all positions $(x, y)$ with $|x|+|y|\le 2$ apart from $(1, 1)$ (which is on the peak). One can compute that there exist $19\,999\,999\,999\,999\,999\,931\,533\,333\,333\,333\,333\,863\,441$ reachable positions in $10^{20}$ seconds and this number is approximated by $2\cdot 10^{40}$ with a relative error smaller than $10^{-6}$. The sample output shows $2\cdot 10^{40}$ as correct answer, but also the exact number of reachable positions would be a correct answer.