P15756 [JAG 2025 Summer Camp #1] Chairs

There are $HW$ chairs arranged in $H$ rows and $W$ columns. We denote the chair in the $i$-th row from the top and the $j$-th column from the left by $(i, j)$. Some chairs may have luggage placed on them. The situation of the chairs is represented by $H$ strings $S_1, S_2, \ldots, S_H$, each of length $W$. If the $j$-th character of $S_i$ is ‘#’, then there is luggage on $(i, j)$. If it is ‘.’, then there is no luggage on $(i, j)$. It is guaranteed that there is at least one chair on which there is no luggage. We want to seat people on these chairs. At most one person can sit on each chair, and a person cannot sit on a chair that has luggage on it. Moreover, two people cannot sit on chairs that are adjacent to each other vertically or horizontally. Under these conditions, we want to seat as many people as possible. Let $M$ be the maximum number of people we can seat observing these rules. Now, suppose one person arrives. For each chair, determine whether we may seat this person there. Specifically, determine whether it is possible to seat this person on that chair, and in addition, still be able to seat $M - 1$ more people under the rules.

The input is given in the following format: $$\begin{aligned} &H \ W \\ &S_1 \\ &S_2 \\ &\vdots \\ &S_H \end{aligned}$$ - $1 \leq H \leq 400$ - $1 \leq W \leq 400$ - $S_i$ is a string of length $W$ consisting of ‘#’ and ‘.’ ($1 \leq i \leq H$). - There exists $(i, j)$ such that the $j$-th character of $S_i$ is ‘.’. - $H$ and $W$ are integers.

Output $H$ lines. On the $i$-th line ($1 \leq i \leq H$), output a string of length $W$. For each $(i, j)$, if we can seat the newly arrived person on $(i, j)$, then the $j$-th character of the string on the $i$-th line must be ‘1’. Otherwise, it must be ‘0’.