Hello. There is a task "Military Base" :

An image of a top-secret military base of an alleged enemy was obtained from a spy satellite in a certain wave range. The base is located on Antarctica, all buildings on it are carved from ice cubes and have a square shape in the photo and do not have common fragments of walls of non-zero length (apparently, this was done in order to disguise from locators operating in the infrared spectrum). Thanks to the skill of the operators, it turned out that the walls of different buildings are parallel to the photo borders.

In order to make an urgent report to the command, you need to know how many buildings are located at the base. Write a program that will do this.

Input data

The first line of the input file INPUT.TXT contains the numbers N and M (1 <= M, N <= 500) - the size of the photo in pixels vertically and horizontally. The following N lines contain M characters each: the '.' corresponds to empty space, '#' - to the element of construction.

Output

In the output file OUTPUT.TXT output a single number - the number of buildings on the base.

There are no ideas how to write it. Is it appropriate to search in width? Write the implementation of the search in width and depth in a two-dimensional array. Thank.

  • @ username76 Read about width and depth rounds e-maxx.ru - andrybak

2 answers 2

I can hardly see how you can use the search in the width or in the glass, this is not a tree structure. Immediately I can offer this solution: read the lines, in the line you look for the characters "#" only if there are several of them, this means the beginning of construction (wall). Next, read the new line, looking for the same in it. If found, then the construction is over, increment the counter. You can start some vector where to add the beginning and end of the wall and check the same coordinates in the vector after each reading.

  • why not tree? very treelike - andrybak
  • @ username76 is usually a wide search on a two-dimensional field (labyrinths, etc.) is called a "wave algorithm" or "fill method", and nobody will write code for you here - andrybak
  • Thank you, I did not ask to write in full for me. - username76

You go around all the elements of the array in order while doing the following: check whether the element is a wall, if yes then check 4 elements of the array on the cardinal points (4 pieces) if any element of the array is indexed, then you assign this index to the current element, if not You assign the current index and at the same time increment it. The quantity at the output will be an index - 1.