2010年8月21日 星期六

352 - The Seasonal War

老虎村與大象村兩邊的居民又在打仗了,上個月大象村成功地發射間諜衛星「鳥鳥號」(Bumble Scope)到對方的領空,發射鳥鳥號的目的在於窺視老虎村上空有幾隻"戰鬥鷹(War Eagles)",然而因為品管不良導致鳥鳥號有兩個瑕疵,首先,在它品質不佳的主鏡頭上摻有許多小蟲,會使照出來的衛星照片有許多小污點,另外由於對焦功能異常,使得照片的大小與銳度變得無法控制。

程式設計師們被一群披著虎皮的大象挾持,把他們囚禁在旅館內逼他們要解決衛星照片失真的問題。失真的照片以每一點的像素(pixel)儲存在檔名為Bumble.in的檔案中,每張照片皆為正方形且每一個"像素"或"點"的資訊不是0就是1。如果一點的像素為1,表示鳥鳥號照像機照到了一整隻戰鬥鷹或只是一隻鷹的一小部份;若像素為0,可能只是因為鏡頭上的污點,或是根本什麼都沒照到,程式設計師們必須假定:

a)
一隻戰鬥鷹至少佔一個點(或像素)。

b)
像素為1相鄰的兩點表示同一隻鷹(相鄰包括上下左右與四個斜角),一張戰鬥鷹的特寫可能會是整張都為1的圖。

c)
不同的兩隻鷹不會彼此靠在一起,雖然這個假設很沒有根據,不過程式設計師們也只能作這樣的假設。

d)
照片的左邊不會循環到右邊,上邊不會循環到下邊,彼此並不相鄰 (當然,如果只有左右兩行,則左行當然與右行相鄰)。

Input and Output

從輸入中讀取一張照片的資訊,第一個整數代表照片的大小,照片由0與1所構成,請計算圖上有幾隻戰鬥鷹。請參考下面的Sample input。

請依照Sample output的格式輸出照片的編號與戰鬥鷹的數目,照片大小不會超過25像素。

Sample input

6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000

Sample output

Image number 1 contains 3 war eagles.
Image number 2 contains 6 war eagles.

原文出處

沒有留言:

張貼留言