Двумерный массив, задача. Помогите разобраться

#java

                    
Дан двумерный массив N*N, который содержит несколько прямоугольников.
Различные прямоугольники не соприкасаются и не накладываются.
Внутри прямоугольник весь заполнен 1-ками.
В массиве:

1) a[i, j] = 1, если элемент (i, j) принадлежит какому-либо прямоугольнику

2) a[i, j] = 0, в противном случае. getRectangleCount должен возвращать количество
прямоугольников.

Метод main не участвует в тестировании:

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;
    }
}

    

Ответы

Ответ 1

Задача довольно несложная. Метод - делаем почти также, как если бы делали на листочке:

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;
}


Вывод программы:


  count = 2. Должно быть 2


¯ \ _ (ツ) _ / ¯