44 уровень

19.08.2021
844просмотров
10комментариев

вопрос

Вопрос по задаче

Решен

не понимаю,что не так указываю ищу нижний правый угол: правый элемент 0

a[i][j+1] == 0

нынешняя строчка j является границей

j== a.length-1

проверка нижнего элемента

a[i+1][j] == 0

проверка что столбик закончился

i== a.length-1

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 не участвует в тестировании

Требования:

В классе Solution должен существовать метод getRectangleCount с одним параметром типа byte[][].
Метод getRectangleCount должен быть публичным.
Метод getRectangleCount должен быть статическим.
Метод getRectangleCount должен возвращать количество прямоугольников (в соответствии с заданием) найденное в полученном массиве.

package com.javarush.task.task20.task2026; /* Алгоритмы-прямоугольники */ public class Solution { public static void main(String[] args) { byte[][] a1 = new byte[][]{ {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 1} }; byte[][] a2 = new byte[][]{ {1, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 1} }; int count1 = getRectangleCount(a1); System.out.println("count = " + count1 + ". Должно быть 2"); int count2 = getRectangleCount(a2); System.out.println("count = " + count2 + ". Должно быть 4"); } public static int getRectangleCount(byte[][] a) { int count=0; for (int i=0;i<a.length-1;i++) { for(int j=0;j<a[i].length-1;j++) { if(a[i][j] == 1 && a[i][j+1] == 0||j== a.length-1 && a[i+1][j] == 0||i== a.length-1) { count++; } } } return count; } }

Комментарии (10)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Павел Безумный учёный

Expert

20 августа 2021, 12:08

Для достоверного определения нижнего правого угла прямоугольника необходимо, чтобы одновременно выполнялись следующие три условия: - значение в текущей ячейке равно 1; - значение в ячейке справа от текущей равно 0 ИЛИ ячейки справа не существует; - значение в ячейке снизу от текущей равно 0 ИЛИ ячейки снизу не существует. Лучше всего первое (главное) условие задать в операторе if, и затем в его теле выполнить обработку второго и третьего условий (например, при помощи тернарных операторов).

Hanyuu

Уровень 44

20 августа 2021, 20:06

я не понимаю как в теле записать тернарник с 4 свойствами , да и как обозначить несуществующую ячейку я не знаю(могу только отталкиваться от того что текущая - конец)

public static int getRectangleCount(byte[][] a) {
        int count = 0;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a[i].length - 1; j++) {
                if (a[i][j] == 1) {
                    if( a[i][j + 1] == 0 || j == a.length - 1 && a[i + 1][j] == 0 || i == a.length - 1) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

я пыталась составить сигнатуру , но не вышло

for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a[i].length - 1; j++) {
                if (a[i][j] == 1) {
                    a[i][j + 1] == 0 || j == a.length - 1 ? count++ : count;
                    a[i + 1][j] == 0 || i == a.length - 1 ? count++ : count;
                    }
                }
            }

Павел Безумный учёный

Expert

20 августа 2021, 20:21

Рассмотрим на примере проверки ячейки, находящейся справа от текущей. Вне зависимости от того, существует ли эта ячейка или нет, нам необходимо получить какой-то результат проверки. Введём дополнительную переменную для удобства:

if (a[i][j] == 1) {
    int right = (i + 1 == a.length) ? 0 : a[i + 1][j];
}

Если ячейки справа от текущей не существует, то результатом проверки будет ноль. Если же ячейка справа имеется в наличии, то результатом выражения будет хранящееся в ней значение. Аналогичным образом проверяется ячейка, находящаяся снизу от текущей. После выполнения этих проверок остаётся только оценить полученные результаты: если оба они равны нулю, то можно утверждать, что обнаружен угол прямоугольника.

Hanyuu

Уровень 44

20 августа 2021, 23:27

несуществующая ячейка имеет вполне существующий результат...такого я не предполагала но что-то у меня не сходится и почему a.length не выходит за пределы матрицы?

public static int getRectangleCount(byte[][] a) {
        int count=0;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a[i].length - 1; j++) {
                if (a[i][j] == 1) {
                    int right = j + 1 == a.length ? 0 : a[i + 1][j];
                    int down = i + 1 == a.length ? 0 : a[i][j + 1];
                    if(right==0 && down==0) count++;
                }
            }
        }
        return count;
    }
}

Павел Безумный учёный

Expert

20 августа 2021, 23:45

решение

Вы на верном пути)

for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a[i].length; j++) {
        if (a[i][j] == 1) {
            int down = i + 1 == a.length ? 0 : a[i + 1][j];
            int right = j + 1 == a[i].length ? 0 : a[i][j + 1];
            if (right == 0 && down == 0) count++;
        }
    }
}

Оба цикла должны проходить по всем без исключения элементам матрицы, то есть i < a.length и j < a[i].length. Сам выход за пределы массива не происходит, поскольку мы делаем проверки i + 1 == a.length и j + 1 == a[i].length, то есть как раз на последнем шаге каждого из циклов. Ведь, к примеру, если i + 1 == a.length, это означает, что текущая ячейка имеет индекс a.length - 1, то есть это последняя ячейка в массиве.

+11

Hanyuu

Уровень 44

21 августа 2021, 00:11

a[i].length ведь тоже самое что и a.length ? или могло бы быть так i <= a.length-1, я кажется поняла, что внесло неразбериху, спасибо) ／/　　　 /　 ;　　　。|　　: 　　|　　　'i,　૮₍ ⸝⸝´ ˘ `⸝⸝ ₎ა ☆　 ‘i　　　ﾄ､_( ヽ∩∩ ) ___ ,　　. 　.　　'i　　　　￣￣￣￣　　;’ 　　　　丶,　　　　　　　,／　　。ﾟ　☆ 　。ﾟ　　　　’ ｰ- - - - ‘´´

Павел Безумный учёный

Expert

21 августа 2021, 00:18

На здоровье 🙂 a[i].length будет равняться a.length только в том случае, если матрица a квадратная. В общем случае для прямоугольной матрицы a.length - это высота матрицы, а a[i].length - её ширина.

bprint

Уровень 41

14 сентября 2021, 10:15

for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a[i].length; j++) {
        if (a[i][j] == 1) {
            int right = i + 1 == a.length ? 0 : a[i + 1][j];
            int down = j + 1 == a[i].length ? 0 : a[i][j + 1];
            if (right == 0 && down == 0) count++;
        }
    }
}

Я бы здесь down и right поменял бы местами.

Павел Безумный учёный

Expert

14 сентября 2021, 10:45

Верно подмечено, исправил в "Решении".

Тимофей ФилипповJava Developer в Снэп-Айти

18 июня 2022, 07:12

вспомнил как в играх делал обходы матрицы и вроде всё правильно написал, но никак не мог понять чего ж у меня исключение переполнения. а просто вместо >a.length надо было == поставить. Спасибо =)