TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

60.5% (46/76)

Tags

Description

在一塊 $N\times N$ 的白布上,固定的位置上有幾支滴墨管。墨水的顏色有黃色(Yellow),藍色(Blue),以及紅色(Red)。按照一般彩色混色的原理如圖三,等量的黃色與藍色可以混出綠色;黃色與紅色則可以混出橘色。當一個地方被三種顏色染色時,則白布呈現黑色。顏色代碼分別是 (R=紅色,Y=黃色,B=藍色,O=橘色,G=綠色,P=紫色,D=黑色)。

當墨水被滴到白布上時,墨水會以一定的速度擴散開來。為了簡化問題,讓我們假設擴散的方式是以正方形的方式進行。如下途中,在一個白布上點了藍色的墨水,在時間 $t=0$ ,只有中間一個籃點。等到 $t=1$ 時,藍色則會擴散到如右圖的範圍。

假設白布的左下角空白格座標為 $(0,0)$,而且所有滴墨管同時於 $t=0$ 的時間滴下墨水。下圖是一個擴散的例子:滴黃色於 $(1,1)$,藍色於 $(3,3)$,紅色於 $(4,0)$。

給你一塊白布、三支滴墨管(紅,黃,藍各一支)的座標以及一個顏色 $X$。請你寫一個程式告訴我們顏色 $X$ 在白布曾出現過的最大面積為何?在上述擴散例子中,顏色 $Y$ 曾出現的最大面積為$8$。

Input Format

輸入的第一行包含一個整數 $T (T \leq 5)$ ,代表接下來有 $T$ 筆測試資料。

每筆測試資料包含五行,每行代表的意義如下:


  • 第一行有一個正整數 $N(N\leq 1000)$, $N$ 代表白布邊長。
  • 第二行到第四行是每行依序顯示墨水管的顏色以及座標位置(顏色與座標值以一個空白分開)。
  • 第五行為顏色 $X$。顏色 $X$可以是 (R,Y,B,O,P,G,D) 其中的任何一色。

Output Format

對於每筆測試資料輸出顏色 X 在白布上曾出現過的最大面積。

Sample Input 1

2
5
Y 1 1
B 3 3
R 4 0
Y
5
Y 1 1
B 3 3
R 4 0
G

Sample Output 1

8
9

Hints

Problem Source

NEOJ Problem 46

台北縣 98 資訊學科能力競賽

Subtasks

No. Testdata Range Constraints Score
1 0~5 $N\leq 100$ 40
2 6~9 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1
1 1000 131072 65536 1
2 1000 131072 65536 1
3 1000 131072 65536 1
4 1000 131072 65536 1
5 1000 131072 65536 1
6 1000 131072 65536 2
7 1000 131072 65536 2
8 1000 131072 65536 2
9 1000 131072 65536 2