回分類題庫
g009: C.怪物辨識
關鍵字: NPSC 2005 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 70 Times / 64 Users | Submit : 155 Times / 68 Users | Accepted rate : 94%
題目加入時間 : 2011-12-06 10:05

Content: 简体中文

在楓之谷這樣一個線上遊戲裡,大家最常做的事情就是不停地打怪物,賺經驗值,然後升級。有的人厭倦這樣的遊戲模式,或是想要偷懶,就想不照著規矩來玩,他們就使用外掛程式來幫他們做這樣的事。只要把外掛程式開著,他可能可以去讀書,或做其他的事情,而這支程式就一直乖乖地,重覆一樣的動作,走幾步,然後砍幾刀,再走幾步,撿撿寶物等等。等到他回來以後,就已經升級了。

這樣作弊的行為是不應該的,雖然只是個遊戲,也有它的道德應該持守著。幾經改版之後,這個遊戲裡提供一種叫作「測謊機」的道具,只要在遊戲中看到疑似用外掛程式在打怪物的人,就可以對他使用。可是你實在覺得遊戲的「測謊機」不甚高明,外掛仍然到處都是。為了讓軟體公司能再加強防堵外掛,你決定親自撰寫程式,以提供一個可以迴避「測謊機」試驗的外掛程式給軟體公司參考。

理想的的外掛程式要在外在行為完全像人一樣。而人和一般的外掛程式最大的不同之處,就是人沒事不會亂揮武器,而是等到怪物接近的時候才會發出攻擊,所以說,這裡有一個關鍵的技術,就是如何能夠認出身邊的怪物。

為了讓問題單純一點,我們讓所有的圖片都變成黑白的。輸入資料裡,前半部是所有已知怪物的長相。每一種怪物的長相都以一個包含「0」、「1」、「-」三種符號的長方形區塊表示。「0」 表示那一個點應該是白的,「1」 表示那一個點應該是黑的,而「-」則表示那一個點不重要。(假使一個點位於怪物的輪廓之外,則該點會隨著背景變動,因此要直接略過檢查這些點)。

在輸入資料的後半部,會有許多張測試的圖片。測試的圖片只會由 0 和 1 兩種符號組成。你應該把測試圖片拿去和每一種怪物的長相作比較,看看和哪一張最像。像的標準定義如下:對圖片上每一個點逐點作比較,如果怪物圖片中對應的點是「-」的話就跳過,統計其餘怪物圖片與測試圖片正確(吻合)和不正確(不吻合)的點數。當正確的點數大於或等於 4 倍不正確的點數的話,則判定比對測試圖片和怪物圖片的結果為吻合。如果一張測試圖片吻合於任何一種怪物時,請輸出Y於一列中。若否,請輸出N於一列中。

Input:

你的程式必須讀入一個輸入檔,檔案的第一列會有四個整數,第一個整數m表示怪物圖片的張數,第二個整數n表示測試圖片的張數 (怪物和測試的圖片都不會超過 10 張)。第三個整數表示這些圖片的寬度,第四個整數表示這些圖片的高度 (所有的圖片都一樣大,測試圖片的寬或高都不會超過 40)。第2行開始依序是m張怪物的圖片,然後是n張測試圖片。

Output:

對每一張測試圖片,請輸出一列 Y 或 N,表示該測試圖片是否吻合任一張怪物圖片。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2 2 32 29
--------------------------------
--------------------------------
--------------------------------
--------------------------------
-----------------1111-----------
----------------1----1----------
---------------1------1---------
--------------11-------1--------
-------------1001------1--------
------------100001-----1--------
-----------10000001-----1-------
---------11000000001----1-------
------111000000000001---1-------
----1100000000000000011-1-------
--11000000000000000000011-------
-100010000000000000000011-------
-100101000000000000000001-------
1000101000000011100000001-------
10000100100000101000000001------
10000000111000111000000001------
10000000010000000000000001------
10000000000000000000000001------
1000000000000000000000001-1--11-
-100000000000000000000001--11101
-10000000000000000000001-----11-
--100000000000000000001---------
---1100000000000000001----------
-----1100000000000111-----------
-------11111111111--------------
------------111111111-----------
----------1100000000011---------
---------100000000000001--------
------1110000000000000001-------
----1100000000000000000001------
--110000000000000000000001------
-10000000000000000000000001-----
-1000000000000000000000000011---
100000111110000000000000000001--
1000110011111111111100000000001-
1001000100000000000011000000001-
10010010000000000000001000000001
-1010010111000000011000100000001
-1001100111000010111100010000001
--100100000011110011000011100001
---1110000000000000000000101001-
----100000000000000000000101001-
---100000000000000000000010111--
--1000000000000000000000011-----
--100000000000000000000001------
-10000000000000000000000001-----
-10000000000000000000000001-----
--1000000000000000000000001-----
--100000000000000000000001------
--100000000000000000000001------
---1000000000000000000001-------
----10000000000000000001--------
-----110000000000000111---------
-------1111111111111------------
10111100110101100000101100011110
00111010111101001010100100011101
01011101010100101000001101000010
00011000111010001001110101111111
11101101011001011111110001010101
01111000101000001101111110011011
01011111001101010111001000001110
01010101001100111000111100100110
00010111001001001000100100010000
01100111101010000101111101110010
00000000110100000011010010110001
01101111111000000001011011101000
00010111100000000000100010001101
00011100000000000000011010001110
01110000000000000000000110011100
11000100000000000000000110010111
11001010000000000000000010110010
10001010000000111000000010000100
10000100100000101000000001010000
10000000111000111000000001001011
10000000010000000000000001100010
10000000000000000000000001010001
10000000000000000000000011101111
11000000000000000000000011111101
01000000000000000000000101001110
11100000000000000000001000100010
00011000000000000000010111100101
10111110000000000011101011011011
11100111111111111111001101000110
10111100110101100000101100011110
00111010111101001010100100011101
01011101010100101000001101000010
00011000111010001001110101111111
11101101011001011100010101010111
10001010000010111110011011010111
11001101001110000000111001010101
00110010001110010011000010111001
00000100000100000110011110100111
10111001000000000110101000110001
01101111101101101000000101000000
11010001000011100100111001001011
11011001000001000100000010111000
10010001101111100100101100010001
00000111100101101110101101101111
10011110011010001100100111110101
10000100100000000001001010111100
01000101101101100000010011111011
10111110101101001001111001111100
11100001111101111110000110001100
00010001110001111011100001110110
11101010100010100101100111010100
01011111101100101100001111110110
01101110101101100100100011000100
10001100101010010001000010011010
00011111101011111100100000100101
11000011001110010111110011010001
11011101011101000110010110110110
01110010100110100100000101100001

Sample Output :

Y
N

Hint :

Author :

NPSC 2005 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum