Problem : 283 - Grid coloring

Special Judge

Problem Statistics

Solved Member: 5　　Submission: 29　　User Tried: 6

Statement:

瀚瀚有一個長方形的格子，一共 n 列 m 行，任意兩個相鄰的格子(有共用邊)之間有一個符號，等於或者不等於，如下圖所示。

瀚瀚希望在每個格子中填入 1 到 k 共 k種數字，若兩相鄰格子的符號是等於，並且填的數字相同，他就會得 1 分，或者，兩相鄰格子符號為不等於，且填入數字不同也會得 1 分。他希望他得的分數至少要有滿分的 $\frac{3}{4}$ 倍以上。

如上圖，每種顏色代表一種不同的數字，用打勾來表示有得分的位置，打叉代表沒得分。瀚瀚一共得了 13 分，最大的分數為 17 分。因此 $\frac{13}{17} \ge \frac{3}{4}$，滿足要求。

Input:Output:

測試資料的第一行有 3 個整數，n,m,k ，代表矩形的列數、行數、以及瀚瀚可以填的數字有幾種。

接下來共有 2n-1 行，每一行依序有 m-1,m,m-1,m, ...,m-1 個字元。字串中有 N,E 兩種字母， N 代表不等於，E 代表等於。

輸入由上到下的順序為圖中符號的排列方法(請見範測及上面的圖)。

限制：
n,m ≤ 1000
k ≤ n*m

20% 的測試資料滿足： n,m ≤ 4
50% 的測試資料滿足： n,m ≤ 100

若沒有辦法得到 $\frac{3}{4}$ 以上的分數，請輸出一行 "NO" 即可。
否則，請在第一行輸出 "YES"。
並輸出 n 列，每一列有 m 個在 1 和 k 之間的數字，代表每一格所填入的數字。

若有多種方法可以得到滿分的 $\frac{3}{4}$ 倍以上的分數，請任意輸出一組解即可。

Sample Input:Sample Output:

3 4 4
ENE
NNEE
NEE
ENEN
ENN

YES
1 1 2 2
3 4 1 1
3 3 2 4

HINT:

題目敘述中的圖恰好對應到範例輸入以及範例輸出的情況。

Source:

Codeforces #180

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
1-3	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
2-3	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
3-3	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
4-3	1000ms	65536kb
5-1	1000ms	65536kb	10
5-2	1000ms	65536kb
5-3	1000ms	65536kb
6-1	1000ms	65536kb	10
6-2	1000ms	65536kb
6-3	1000ms	65536kb
7-1	1000ms	65536kb	10
7-2	1000ms	65536kb
7-3	1000ms	65536kb
8-1	1000ms	65536kb	10
8-2	1000ms	65536kb
8-3	1000ms	65536kb
9-1	1000ms	65536kb	10
9-2	1000ms	65536kb
9-3	1000ms	65536kb
10-1	1000ms	65536kb	10
10-2	1000ms	65536kb
10-3	1000ms	65536kb