P10127 "Daily OI Round 3" Tower

Define the `A-distance` between $(x_1,y_1)$ and $(x_2,y_2)$ as $\max\{|x_1-x_2|,|y_1-y_2|\}+1$. All distances mentioned below refer to the `A-distance`. For example, the `A-distance` between $(1,1)$ and $(3,8)$ is $\max\{|1-3|,|1-8|\}+1=8$. For example, the `A-distance` between $(46,1)$ and $(35,9)$ is $\max\{|46-35|,|1-9|\}+1=12$.

The territory of Country A can be seen as an $n\times m$ matrix, where the cell in row $x$ and column $y$ has coordinates $(x,y)$. The land can be mountainous, represented by `#`, or flat, represented by `.`. Country A has built an energy tower on every flat cell. The energy range of an energy tower is a square. If $e$ satisfies that all places whose `A-distance` to this energy tower is **not greater than** $e$ are within the territory of Country A, and those places are flat land, then $e$ is called the base energy of this energy tower. The overall energy $E$ of an energy tower is the maximum possible value of its base energy $e$. In particular, if there is no energy tower at a place, then the overall energy there is $E=0$. Otherwise, the overall energy there equals the overall energy of the energy tower. Let the overall energy at row $i$ and column $j$ be $E_{i,j}$. Let the total energy sum of a country be $\xi=\sum\limits^n_{i=1}\sum\limits_{j=1}^mE_{i,j}^2$. You need to compute the total energy sum $\xi$ of the country. Of course, due to special reasons (such as the effect of cosmic rays), a flat cell may suddenly turn into a mountain. The local energy tower will be destroyed, and this will also affect the overall energy $E$ of nearby energy towers. As an advisor of Country A, the king wants you to prepare a plan: for each non-mountain cell, check what the total energy sum of the country will be after that cell becomes a mountain.

The first line contains two integers $n,m$. Then follows an $n\times m$ matrix. The cell in row $i$ and column $j$ is `#` or `.`, describing the terrain of Country A.

Output a total of $n+1$ lines. The first line contains an integer $\xi$, the initial total energy sum of Country A. Then output an $n\times m$ matrix: the integer in row $i+1$ and column $j$ represents the total energy sum $\xi_{i,j}$ after $(i,j)$ becomes a mountain. In particular, if $(i,j)$ is originally a mountain, output $-1$.

#### [Sample Explanation #1] Here are $3$ examples: At the beginning, $E_{i,j}$ of this country is as follows: ``` 1 1 1 1 1 2 1 0 1 1 1 1 ``` After $(1,1)$ becomes a mountain, $E_{i,j}$ is as follows: ``` 0 1 1 1 1 1 1 0 1 1 1 1 ``` After $(3,4)$ becomes a mountain, $E_{i,j}$ is as follows: ``` 1 1 1 1 1 2 1 0 1 1 1 0 ``` #### [Constraints] For all data: $1\le n,m\le600$. Translated by ChatGPT 5