University of Calgary

target

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
00000
1000010000
200000011110003
200000000000000
0000
44000000000
000000000000000
00
5555000007000
000
550000007000
000000
700007000
00
6007700007700
000000
700007777
00000
7777777777
0000
70000007777
000
700000007777


Updated: August 6, 2005 10:54 AM