P15756 [JAG 2025 Summer Camp #1] Chairs

有 $HW$ 把椅子排列成 $H$ 行 $W$ 列。我们将从上往下数第 $i$ 行、从左往右数第 $j$ 列的椅子记作 $(i, j)$。 一些椅子上可能放有行李。椅子的状况由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示。如果 $S_i$ 的第 $j$ 个字符是 `#`，则表示 $(i, j)$ 上有行李。如果是 `.`，则表示 $(i, j)$ 上没有行李。保证至少有一把椅子上没有行李。 我们想安排人们坐在这些椅子上。每把椅子最多只能坐一个人，且人不能坐在放有行李的椅子上。此外，两个人不能坐在垂直或水平方向上相邻的椅子上。在这些条件下，我们希望尽可能多地安排人就座。设 $M$ 为遵守这些规则所能安排的最大人数。 现在，假设又来了一个人。对于每把椅子，判断我们是否可以让这个人坐在那里。具体来说，判断是否可以让这个人坐在那把椅子上，并且在此之后，仍然能够按照规则再安排 $M - 1$ 个人就座。

输入格式如下： $$\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$ 是一个长度为 $W$ 的字符串，由 `#` 和 `.` 组成（$1 \leq i \leq H$）。 - 存在 $(i, j)$ 使得 $S_i$ 的第 $j$ 个字符是 `.`。 - $H$ 和 $W$ 是整数。

输出 $H$ 行。在第 $i$ 行（$1 \leq i \leq H$），输出一个长度为 $W$ 的字符串。 对于每个 $(i, j)$，如果我们可以让新来的人坐在 $(i, j)$ 上，则第 $i$ 行字符串的第 $j$ 个字符必须是 `1`。否则，必须是 `0`。

翻译由 DeepSeek V3.2 完成