Codeforces Round #724 Omkar and Forest Solution (Java/C++)

Solution:

There are two conclusions:

For any point of the map, assume the value of this point is x. So, there must a path from this point, and the value of all the point of this path is: [x,x-1,x-2,...,2,1,0].
Base on the 2nd condition of this problem, this conclusion is obviously.
From any point of the map which value is 0. After x steps, the value of current point at mot be x.
Base on the 1st condition of this problem, this conclusion is obviously.

Then, for the value of any point which is not 0, we can get the range of the value:

Based on the conclusion 1. We know that $x\geq \min{(dis\_to\_0)}$. So, the x is bigger or equal to the distance of nearest 0 point.
Based on the conclusion 2. We know that the maximum value of x is the distance to the nearest 0 point.

So, we found that: in fact, the value of this point must be equal to the distance to the nearest 0. So, the value of point is decided by the 0 point.

So, we just enumerate which '#' is 0. So, there are: $C_n^0+C_n^1+C_n^2+...+C_n^n=2^n$ ways.
Also, if all point is '#', then we cannot go with $C_n^0$. So, subtract 1.

Code:

Java

C++