[HOJ 283][Codeforces #180]Grid coloring (題目備份)

HSNU Online Judge

• Index
• User
• Problem
  • Vol.0
  • Vol.1
  • Vol.2
  • Vol.3
  • Vol.4
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 283 - Grid coloring

Special Judge

Problem Statistics

Solved Member: 5　　Submission: 29　　User Tried: 6

Problem：

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

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

如上圖，每種顏色代表一種不同的數字，用打勾來表示有得分的位置，打叉代表沒得分。瀚瀚一共得了 13 分，最大的分數為 17 分。因此 1317≥34，滿足要求。

Input：

測試資料的第一行有 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

Output：

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

若有多種方法可以得到滿分的 34 倍以上的分數，請任意輸出一組解即可。

Sample Input：

3 4 4
ENE
NNEE
NEE
ENEN
ENN

Sample Output：

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

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.0312 秒，使用記憶體: 2.87MB 。