回分類題庫
d105: 資料結構98程式1.4
出處:mkshan

Difficulity : 1
Accepted : 53 Times | Submit :364 Times | Clicks : 2138
Accepted : 35 Users | Submit : 93 Users | Accepted rate : 38%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-09-30 15:13

Content :

Keroro的機器人人口預測

「宇宙侵略軍特殊先鋒部隊」(簡稱Keroro小隊)Keroro軍曹領軍,潛入愛爾普藍星。Keroro發現愛爾普藍星上有種特殊的機器人,

1. 機器人所居住的城市都由棋盤式的社區所組成。

2. 每個社區大小都一樣,但社區為k層的等腰三角形。第w層有2w-1個門號。

3. 機器人有兩種型號:滴滴答答。機器人根據特殊的鄰居狀況,有可能會自動關機,也有可能會複製產生新的機器人。所謂的鄰居是指上、下、左、右、左上、左下、右上、右下共8個方向的鄰居。當然,居住在社區邊緣的機器人,鄰居數可能不到8位。

a. 若機器人目前在社區的鄰居數 < 2 > 3,則下一光年就會自動關機。

b. 若機器人目前在社區的鄰居數 = 2 = 3, 則下一光年會繼續維持開機的狀態,除非所有鄰居的型號都與其相同。若所有鄰居的型號都與其相同,則下一光年也會自動關機。

c. 若社區內某個門號在目前這一光年沒有機器人,而此門號的鄰居數 = 3且型號不盡相同(也就是一滴二答或一答二滴),則下一光年會複製產生新的機器人。若是一滴二答,則新機器人型號為滴滴。若是一答二滴,則型號為答答。

d. 每個機器人都有其年限,其年限決定於其誕生前相鄰社區人數的總和。因此,當其到達年限時,也會自動關機。

例如:圖1為一由3 x 4的棋盤社區所組成的城市,每個社區都是底為5的三層等腰三角形。其中,有5個社區編號分別為(1,1), (1,2), (1,3), (2,2), (2,3)住有機器人。以社區(1,3)為例,門號(2,4)有位年限還有3個光年的答答型機器人、門號(3,2)有位年限還有6光年的滴滴型機器人。

(粉紅色代表答答、灰色代表滴滴)

 

2則為一光年後,此城市的機器人分布狀況。其中

a.       (1.3)社區因為原本每個機器人的鄰居都少於2,因此自動關機。

b.      原本(2,2)社區的每個機器人,都有2個鄰居,且鄰居與自己全部都不是同一型的機器人,因此一光年後繼續保持開機的狀態。只是其年限都因此減少了一光年。反觀(1,2)社區,雖然原本每個機器人都有2個鄰居,但因為三者都屬於滴滴型機器人,因此一光年後就自動關機了。

c.       原來(2,2)社區的門號(3,4)位置沒有機器人,但因這位置原來有3個鄰居,且為2滴一答,因此一光年後,複製誕生了一個答答型機器人,且其年限為原來周遭社區的人數總和15

d.      原來(1,1)社區的門號(3,2)位置有個滴滴型機器人,但因其年限為1年,因此一光年後自動關機。

 

給定

1.      一城市的大小i, j、每個社區的層數k

2.      每個機器人所居住的社區編號(u, v)及門號(x, y),型號(pq)及年限r

請列出s光年後,每個社區的機器人個數。

 

Input :

輸入共有1+t行,

1. 1行有4個以空白間隔的整數i, j, k, s。其中,

i, j代表棋盤式城市的長度與寬度,1 <= i, j <= 10

k代表社區的層數,1 £ k £ 5,社區為k層的三角形,w層會有2w-1個門號;

s代表keroro小隊所要做的機器人口預測是s光年後。

2.    接下來t行,每一行有4個整數u, v, x, y,接著一個字元(pq),再接著一個數字r

分別記錄原始t個機器人所居住的社區編號(u, v)及門號(x, y),機器人型號(pq)及年限r。其中

1 <= u <= i, 1 <= v <= j, 1 <= x <= k, k-x+1 <= y <= k+x-1, 1 <= r <= 8k2.

Output :

輸出共有i行,每行有j個以空白間隔的數字,

分別代表每個社區s光年後的的機器人人數

Sample Input :

3 4 3 1
1 1 2 3 p 2
1 1 2 4 p 1
1 1 3 2 p 1
1 1 3 3 q 5
1 1 3 4 p 2
1 1 3 5 q 3
1 3 2 4 q 3
2 2 2 4 p 3
1 3 3 2 p 6
2 2 2 3 q 2
2 2 3 3 p 2
3 3 2 2 q 2
3 3 2 4 p 2
3 3 3 1 q 2
3 3 3 3 q 3

Sample Output :

2 0 0 0
0 4 0 0
0 0 2 0

Hint :


  

Author :

mkshan

  Solve it!   Status Forum (0)

C++
C
JAVA
57045. johnny (8 ms , 378KB)
33549. ds100 (8 ms , 308KB)
52807. s10103 (10 ms , 398KB)
24901. oop98703015 (2 ms , 414KB)
24888. henryokc (2 ms , 364KB)
8561. nipa (2 ms , 324KB)
57009. ag100 (4 ms , 386KB)
56976. ag100 (4 ms , 388KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡