package com.javarush.test.level20.lesson10.bonus02;

/* Алгоритмы-прямоугольники
1. Дан двумерный массив N*N, который содержит несколько прямоугольников.
2. Различные прямоугольники не соприкасаются и не накладываются.
3. Внутри прямоугольник весь заполнен 1.
4. В массиве:
4.1) a[i, j] = 1, если элемент (i, j) принадлежит какому-либо прямоугольнику
4.2) a[i, j] = 0, в противном случае
5. getRectangleCount должен возвращать количество прямоугольников.
6. Метод main не участвует в тестировании
*/
public class Solution {
    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) {
        byte[][] catched = new byte[a.length][a[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                catched[i][j] = 0;
            }
        }
//                {
//            {0, 0, 0, 0},
//            {0, 0, 0, 0},
//            {0, 0, 0, 0},
//            {0, 0, 0, 0}
//        };    //матрица "погашенных" прямоугольников
        int rectangleCount = 0;    //счётчик прямоугольников
        boolean isCatched = false;    //прямоугольник пойман
        int beginX = 0;
        int finishX = 0;    //координаты пойманного прямоугольник по оси X

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] == 1 && catched[i][j] != 1) {    //если клетка не пустая и ещё не погашена
//                    catched[i][j] = 1;    //гасим клетку
                    if (!isCatched) {    //если при этом мы не в режиме пойманного прямоугольника
                        isCatched = true;    //переключаемся в режим
                        beginX = j;    //помечаем клетку начала следующей итерации
                    }
                }
                if ((a[i][j] == 0 && isCatched) || (j == a[i].length - 1 && isCatched)) {    //если заступили за границу прямоугольника (включён режим поиска)
                    if (a[i][j] == 0 && isCatched) finishX = j;    //помечаем клетку окончания следующей итерации
                    else finishX = j + 1;
                    for (int l = i; l < a.length; l++) {    //вычисляем прямоугольник
                        for (int k = beginX; k < finishX; k++) {    //бежим по линии прямоугольника
                            if (a[l][k] == 1) catched[l][k] = 1;    //если это ещё прямоугольник
                        }
                        if (l == a.length - 1 || a[l + 1][beginX] == 0) {
//                            System.out.printf("catched: %d, %d%n", l, beginX);    //треугольник пойман
                            rectangleCount++;
                            isCatched = false;
                            break;
                        }
                    }
                }
            }
        }
//        for (byte[] aCatched : catched) {    //вывод матрицы погашеных клеток
//            for (byte anACatched : aCatched) {
//                System.out.print(anACatched);
//            }
//            System.out.println();
//        }
        return rectangleCount;
    }
}