Given a two-dimensional array of N * N, which contains several rectangles. Different rectangles do not touch or overlap. Inside the entire rectangle is filled with 1-kami. In the array:

1) a [i, j] = 1, if the element (i, j) belongs to some rectangle

2) a [i, j] = 0, otherwise. getRectangleCount should return the number of rectangles.

The main method does not participate in testing:

 public class ArrayWithRectsGetThemCount21032016 { public static void main(String[] args) { byte[][] a = new byte[][]{ {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 1} }; int count = getRectangleCount(a); System.out.println("count = " + count + ". Должно быть 2"); } public static int getRectangleCount(byte[][] a) { return 0; } }
  • Very interesting. Please tell us what you have already achieved in addition to return 0; . - Igor
  • Nothing yet ...) - Kostya Batrak
  • Hmm, well, do you have any thoughts? Here you begin to check the elements of the array in a loop, and you meet the unit ..? - Igor
  • if we find a unit, then we find the beginning of the rectangle, and how to determine its boundaries and exclude the found rectangle from the search? - Kostya Batrak
  • one
    ... we go further along this line. Somewhere units (or line) must end - then we found the width of this rectangle. Come on, let's, what do you have to pull out every word from you? - Igor

1 answer 1

The task is quite simple. Method - we do almost the same as if we did on a piece of paper:

 public static void main(String[] args) { byte[][] a = new byte[][]{ {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 1} }; int count = getRectangleCount(a); System.out.println("count = " + count + ". Должно быть 2"); } public static int getRectangleCount(byte[][] a) { int count = 0, tmp = -1, jt = a[0].length; boolean findRect = false; while (tmp != count) { //если счётчик увеличился за проход по матрице - снова делаем проход по матрице tmp = count; outerloop: for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[0].length; j++) { if (a[i][j] == 1 && !findRect) { //случай, когда встретили прямоугольник count++; jt = j; //запоминаем столбец, в котором начался прямоугольник findRect = true; a[i][j] = 0; } else if (a[i][j] == 1 && findRect) {//обнуляем, чтобы не мешался a[i][j] = 0; } else if (a[i][j] == 0 && findRect && j == jt) { //если элемент под прямоугольник равен 0 - он закончился break outerloop; //выходим из внешнего цикла } else if (a[i][j] == 0 && findRect && j > jt) { //если элемент справа от прямоугольника равен 0 - идем на след строку break; } } } findRect = false; } return count; }

The output of the program:

count = 2. Must be 2

¯ \ _ (ツ) _ / ¯