Решил использовать HashMap для построчной записи координат ячеек, которые принадлежат к прямоугольникам, а далее сравнивать ряд с предыдущим и фиксировать изменения в координатах как +прямоугольники.
Да, время O(n), но не придумал как сделать без полного перебора ячеек.
По идее должно работать, но на своем примере массива а3 - не работает корректно. Ну и валидатор соответственно не принимает.
Подскажите, в чем ошибка?
package com.javarush.task.task20.task2026;
/*
Алгоритмы-прямоугольники
*/
import java.util.HashMap;
import java.util.Map;
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}
};
byte[][] a3 = new byte[][]{
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 1, 1, 1},
{1, 1, 0, 1, 1, 0, 0, 1, 1, 1},
{1, 1, 0, 1, 1, 0, 0, 1, 1, 1},
{1, 1, 0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
int count1 = getRectangleCount(a1);
System.out.println("count = " + count1 + ". Должно быть 2");
int count2 = getRectangleCount(a2);
System.out.println("count = " + count2 + ". Должно быть 4");
int count3 = getRectangleCount(a3);
System.out.println("count = " + count3 + ". Должно быть 8");
}
public static int getRectangleCount(byte[][] a) {
// если массив одинарный
if (a.length == 1) {
return a[0][0];
}
int result = 0; // для подсчета обнаруженных прямоугольников
// переменная указывает находимся ли мы "внутри" треугольника во время прохода по массиву
boolean switcher = false;
// для обозначения границ прямоугольников в предыдущем ряду
HashMap<Integer, Integer> previousPairs = new HashMap<>();
// для обозначения границ прямоугольников в текущем ряду
HashMap<Integer, Integer> currentPairs = new HashMap<>();
for (int i = 0; i < a.length; i++) {
// перед обходом очередного ряда очищаем карту с обозначениями кородинат, принадлежащих
// к прямогуольникам
currentPairs.clear();
// обрабатываем очередной ряд массива и отмечаем какие координаты принадлежат
// прямоугольникам, а какие - нет
for (int j = 0; j < a[i].length; j++) {
int begin = 0;
int end = 0;
if (a[i][j] == 1 && !switcher) { // если попали на координату прямоугольника
begin = j; // и переключатель не включен, то записваем
switcher = true; // ячейку как начало прямогульника
}
if (a[i][j] == 1 && j == a[i].length - 1) { // если прямогульник примыкает к границе
end = j; // матрицы, то записываем как конечную
currentPairs.put(begin, end); // координату, выключаем переключатель
switcher = false;
}
if (a[i][j] == 0 && switcher) { // если вышли за пределы прямогуольника
end = j - 1; // то переключаем выключатель и записываем
currentPairs.put(begin, end); // в карту соответствующую координату
switcher = false;
}
}
// здесь сравниваем координаты прямоугольников текущего ряда с предыдущим
// если они совпадают - прямоугольник пока не знакончился, а если нет - +1 прямоугольник
// ведь у нас прямоугольники не соприкасаются по условию
if (!previousPairs.isEmpty()) {
for (Map.Entry<Integer, Integer> entry : previousPairs.entrySet()) {
if (!currentPairs.containsKey(entry.getKey())) {
result += 1;
}
}
}
// для последнего ряда - просто подсчитываем количество прямоугольников, которые
// не закончились ранее и примыкают к "низу" матрицы. Благо информация о них
// записана как пара "ключ-значение" в currentPairs
if (i == a.length - 1) {
result += currentPairs.size();
} else {
// previousPairs инициализируем значениями currentPairs,
// координаты текущего ряда записываются как координаты предыдущего
synchronizeMaps(previousPairs, currentPairs);
}
}
return result;
}
private static void synchronizeMaps(Map<Integer, Integer> map1, Map<Integer, Integer> map2) {
// Используем keySet() для получения множества ключей первой карты
// И затем removeIf() для удаления ключей, которых нет во второй карте
map1.keySet().removeIf(key -> !map2.containsKey(key));
// Используем keySet() для получения множества ключей второй карты
// И добавляем их в первую карту, если их там ещё нет
for (Map.Entry<Integer, Integer> entry : map2.entrySet()) {
Integer key = entry.getKey();
Integer value = entry.getValue();
if (!map1.containsKey(key)) {
map1.put(key, value);
}
}
}
}