target

from: CC Small College Computing Conference 5th Programming Contest

Target identification is an important application in military software systems, among other things. Data from satellite images are encoded in a machine readable form, and software is then used to interpret this data. Your task is to write a program that inputs satellite images as a text file of zeroes and ones and returns the total number of enemy targets present in the image. Targets can be identified as any collection of one or more ones connected horizontally, vertically, or diagonally. Thus an image file consisting of all ones represents a single (albiet large) target.

Input consists of a single integer N, followed by an N x N square matrix of ones and zeroes. Your program only has to print a count of the regions. The exmaple below is simply to show what regions there are. Out put to this program would be something like:

There are 7 targets in the current image.

Example:		with 'targets' marked:
15
000001111010000 000001000010000 100000011110001 100000000000000 000011000000000 000000000000000 001111000001000 000110000001000 000000100001000 001001100001100 000000100001111 000001111111111 000010000001111 000100000001111		000001111010000 000001000010000 200000011110003 200000000000000 000044000000000 000000000000000 005555000007000 000550000007000 000000700007000 006007700007700 000000700007777 000007777777777 000070000007777 000700000007777

Updated: August 6, 2005 10:54 AM