CF297D Color the Carpet

即使是北极熊躺在冰上也会觉得冷。因此，一只名叫 Alice 的北极熊打算制作一块地毯。这个地毯可以看作是一个高为 $h$、宽为 $w$ 的网格，然后被分成 $h \times w$ 个方格。Alice 打算为每个方格涂上 $k$ 种不同颜色中的一种，颜色编号从 $1$ 到 $k$。她可以选择不用所有颜色。 然而，涂色有一些限制。对于每一对相邻的方格（即共享一条边的方格）$x$ 和 $y$，都有一个配色约束，形式如下之一： - $color(x) = color(y)$，或者 - $color(x) \neq color(y)$。 配色约束的示意图如下：  理想情况下，Alice 希望满足所有配色约束。但在北极生活其实很艰难，并不总是能做到这点。幸运的是，如果她能满足至少  的配色约束，她也会很开心。 如果她有 $4$ 种颜色，可以按如下方式为地毯涂色：  她很开心，因为满足的配色约束数量为 ，并且 。你的任务是帮助她为地毯涂色。

第一行包含三个整数 $h, w, k$，表示地毯高度、宽度以及可用颜色种数，满足 $2 \leq h, w \leq 1000, 1 \leq k \leq w \cdot h$。 接下来的 $2h-1$ 行描述从上到下、从左到右的配色约束。它们依次包含 $w-1, w, w-1, w, \ldots, w-1$ 个字符。每个配色约束由字符 "E" 或 "N" 表示，"E" 表示 $=$，"N" 表示 $\neq$。 配色约束的顺序与示意图保持一致。

如果存在一种涂色方式，能满足至少  个配色约束，则第一行输出 "YES"（不含引号）。接下来 $h$ 行，每行输出 $w$ 个整数，表示每个方格的颜色编号。 否则输出 "NO"（不含引号）。

由 ChatGPT 5 翻译