Codeforces Round 180 (Div. 1) |
---|
Закончено |
Даже белым медведям холодно лежать на льду. И вот, белая медведица Алиса собралась сделать ковер. Ковер можно рассматривать как сетку с высотой h и шириной w. Затем сетка делится на h × w квадратов. Алиса собирается покрасить в один из k различных цветов каждый квадрат. Цвета пронумерованы от 1 до k. Она может не использовать все доступные ей цвета.
Однако есть ограничения. Для любых двух соседних ячеек (ячеек, имеющих общую сторону) x и y, есть цветовое ограничение в одной из следующих форм:
Пример цветовых ограничений:
В идеале Алиса хочет удовлетворить всем цветовым ограничениям. Но как мы уже говорили, жизнь в Арктике — не сахар. Не всегда можно удовлетворить всех цветовым ограничениям. К счастью, медведица все же будет рада, даже если хотя бы цветовых ограничений будут удовлетворены.
Если у Алисы есть 4 цвета, она может раскрасить изображенный на рисунке ковер следующим образом:
И она рада, потому что цветовых ограничений удовлетворены и . Ваша задача — помочь ей раскрасить ковер.
Первая строка содержит три целых числа h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).
Следующие 2h - 1 строк содержат цветовые ограничения сверху вниз, слева направо. Они содержат w - 1, w, w - 1, w, ..., w - 1 символов соответственно. Каждое цветовое ограничение представлено символом «E» или «N», где «E» означает « = », а «N» означает « ≠ ».
Цветовые ограничения перечисляются в том порядке, в котором они изображены на рисунке в условии.
Если существует раскраска, удовлетворяющая по крайней мере цветовых ограничений, выведите в первой строке «YES» (без кавычек). В каждой из следующих h строк выведите по w целых чисел, описывающих раскраску.
В противном случае выведите «NO» (без кавычек).
3 4 4
ENE
NNEE
NEE
ENEN
ENN
YES
1 1 2 2
3 4 1 1
3 3 2 4
Название |
---|