UVA-352 - The Seasonal War

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！

題意概要

題目希望確認畫面中有幾隻老鷹，題目給定一個正方形的畫面大小，並給定在該正方形中老鷹出現的位置，每一格像素 (pixel) 只有 0 或 1 兩種可能，如果是 1 代表為一隻老鷹，且「上、下、左、右」與「斜角四個方向」相連的 1 只能算是同一隻。試求：畫面中總共有幾隻老鷹？

• 分析：本題為簡單的「深度優先搜尋 (DFS)」應用。只要針對畫面中出現 1 的位置進行八個方向的 DFS，即可計算出老鷹的總數。

Input and Output

Write a program that reads images of pixels from the input file (a text file), correctly counts the number of war eagles in the images and prints the image number and war eagle count for that image on a single line in the output file (also a text file). Use the format in the sample output. Do this for each image in the input file. Each image will be preceded by a number indicating its square dimension. No dimension will exceed $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.