Array of arbitrary size:

  • Placing at least one 4x4 building
  • filled with numbers that represent the height of the building (the numbers are positive, the ground is flat, height = 0)

All buildings:

  • Have a positive height
  • Have a rectangular shape
  • Flat upstairs
  • Edges parallel to the coordinate system
  • If the cells touch the corner of another building, then they belong to different buildings.

It is necessary to find the central points of buildings whose size is greater than or equal to 4x4 (3x10 does not fit). Coordinates are rounded down.

The main difficulty is to find these buildings with the condition that their size is at least 4x4

P.S. Tried to do through a bunch of cycles, conditions and additional variables and something did not work out (the algorithm is lame)

  • one
    An example of an array would be - Lexx918
  • prntscr.com/ljseh4 (here, instead of an array, the coordinate axis, but I think it will be clear) - Melliodas
  • Please edit the question and indicate what caused you difficulties in solving the problem - Kromster
  • The main difficulty is to find these buildings with the condition that their size is at least 4x4 - Melliodas
  • 2
    Do not need links, insert all the necessary code for the question into the question. - tym32167

1 answer 1

I downloaded your data file and prepared it for php solution:

 $ar = file(__DIR__. '/level4_0.in'); $ar = array_map('trim', $ar); array_splice($ar, 41, 1); array_splice($ar, 0, 1); $ar = array_map(function($row){ $row = explode(' ', $row); $row = array_map('intval', $row); return $row; }, $ar);

Got a two-dimensional array of the form:

 [ [0, 5, 5, ..], [0, 5, 5, ..], .. ]

The solution to this is:

We're going through the line. In each row we iterate over the columns. We get a cell of the field. If it is NOT empty and above it is empty (or it is the first line), then we understand that we have found the upper left corner of the building. From this place, with two more nested cycles, we first measure the width of the building, and then (if the width is suitable) and the length. Suitable building we remember. In any case (whether the building came up or not), we continue to search for the next building in the same line, but from the place where we finished searching for the first one.

 $found = []; for ($row = 0; $row < count($ar); $row++) { for ($col = 0; $col < count($ar[$row]); $col++) { if ($ar[$row][$col] && (!$row || !$ar[$row - 1][$col])) { for ($c = $col; $c < count($ar[$row]); $c++) { if (!$ar[$row][$c]) { break; } } if (($c - $col) > 2) { for ($r = $row; $r < count($ar); $r++) { if (!$ar[$r][$col]) { break; } } if (($r - $row) > 2) { $found[] = [ "row" => floor(($row + $r) / 2), "col" => floor(($col + $c) / 2), ]; } } $col = $c; } } } echo "found:\n"; foreach ($found as $node) { echo "{$node['row']}x{$node['col']}\n"; }

Result (did not check manually):

 found: 12x32 22x52 32x22 32x42 51x22 51x57 61x42 71x62 81x47

Also did not check the validity of the input data: the "squareness" of buildings, the absence of intersections of buildings or holes inside the building.