P4262 [Code+#3] Platinum Führer and Moscow

> The cold wind blowing in Moscow / as if yesterday’s dream / Ah, will you still remember me? 1941.12. The weather was freezing cold, the army exhausted... The plan to encircle the capital had run into trouble. The air force might be the last hope to salvage the situation, thought Führer Adolf.

In an $n \times m$ grid, there is an army unit that needs resupply. Each cell in the area is either an empty cell or an obstacle. The air fleet needs to dispatch several transport planes to this area. Each transport plane can drop supplies to two adjacent (sharing a common edge) empty cells. To prevent unnecessary damage, a cell marked as empty can receive at most one drop. Due to the weather, the exact location of the army unit cannot be determined. Therefore, for every empty cell, when the army unit is in that cell (treat it as an obstacle), the Führer wants to know the number of different schemes to drop any amount of supplies to the remaining empty cells using any number (possibly $0$) of transport planes. Two schemes are different if and only if there exists a cell that is supplied in one scheme but not in the other, or there exist two supplied cells that are supplied by the same plane in one scheme but not so in the other. If you are still unsure, please refer to the explanation for Sample 1. You need to write a program to compute these values.

Line 1: two space-separated positive integers $n, m$ — the number of rows and columns of the grid region. Next $n$ lines: line $i$ contains $m$ space-separated integers $A_{i1}, A_{i2}, \ldots, A_{im}$ — $A_{ij} = 0$ means the cell in row $i$, column $j$ is an empty cell; $A_{ij} = 1$ means the cell is an obstacle.

Output $n$ lines. Line $i$ contains $m$ space-separated integers $B_{i1}, B_{i2}, \ldots, B_{im}$ — if the cell in row $i$, column $j$ is an empty cell, then $B_{ij}$ is the number of schemes after turning that cell into an obstacle; otherwise $B_{ij} = 0$. Each answer is taken modulo $10^9+7$.

#### Explanation for Sample 1 Take the empty cell in row $2$, column $1$ as an example. After it is changed into an obstacle, the grid is as follows. Cells marked with o are empty, and cells marked with x are obstacles. ``` ｏｏｏｏ ｘｏｏｘ ``` There are $15$ schemes as shown below. Different colors represent the drop positions of different transport planes.  #### Constraints This problem uses bundled tests. The information for each test point is as follows: | Subtask ID | Points | $n$ | $m$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $\le 2$ | $\le 17$ | | $2$ | $8$ | $\le 5$ | $\le 5$ | | $3$ | $6$ | $\le 9$ | $\le 9$ | | $4$ | $9$ | $\le 12$ | $\le 12$ | | $5$ | $17$ | $\le 15$ | $\le 15$ | | $6$ | $17$ | $\le 16$ | $\le 16$ | | $7$ | $33$ | $\le 17$ | $\le 17$ | For all testdata, $1 \leq n, m \leq 17$, $A_{ij} \in \{0, 1\}$. #### Notes *Von allem Anfang an bin ich nur verraten und betrogen worden!* The statement does not fully agree with historical facts. Credit: https://www.luogu.org/discuss/show?postid=35727 Translated by ChatGPT 5