Подсчитайте облака в массиве 2d

Я пытаюсь выяснить эту проблему с помощью CodeFights, но у меня нет большого опыта в обходе графа, поэтому я борюсь. Одним из советов, которые я прочитал для этой конкретной проблемы, был «обход графа», поэтому я сделал BFS, но я не уверен, как получить количество облаков.

По какой-то причине, связанной с этой проблемой и многими другими проблемами, мой разум теряет сознание, когда приходит время писать для нее код. Я подошел к проблеме, пытаясь найти смежные единицы, но безрезультатно. Кто-нибудь может мне помочь?

https://codefights.com/interview/pDTvSuHBgAB9dz5ik/companies/N3sScnJbzdPDQaHPj

Учитывая двумерную карту неба с сеткой, состоящую из единиц (облака) и нулей (чистое небо), подсчитайте количество облаков. Облако окружено ясным небом и образуется путем соединения соседних облаков по горизонтали или вертикали. Можно предположить, что все четыре края карты неба окружены ясным небом.

Пример

skyMap = [['0', '1', '1', '0', '1'],
         ['0', '1', '1', '1', '1'],
         ['0', '0', '0', '0', '1'],
         ['1', '0', '0', '1', '1']]

вывод должен быть countClouds(skyMap) = 2;

skyMap = [['0', '1', '0', '0', '1'],
         ['1', '1', '0', '0', '0'],
         ['0', '0', '1', '0', '1'],
         ['0', '0', '1', '1', '0'],
         ['1', '0', '1', '1', '0']]

вывод должен быть countClouds(skyMap) = 5.


java algorithm data-structures breadth-first-search depth-first-search
person andsec    schedule 13.06.2017    source источник
comment
Я вижу, что даже одна неокруженная ячейка 1 считается облаком. Я ошибаюсь?   -  person Yahya    schedule 13.06.2017
comment
DFS работает так же хорошо. Вы должны сохранить логический массив, который хранит true, если узел был посещен, и false в противном случае. Рекурсивно перемещайтесь по 2D-массиву, каждый раз переходя на уровень глубже, если узел не был посещен. Если узел был посещен, перейдите к следующему, в противном случае увеличьте счетчик и рекурсивно. Остановитесь, когда вы посетили все узлы.   -  person cs95    schedule 13.06.2017
comment
@Yahya Ты прав.   -  person andsec    schedule 13.06.2017
comment
Я бы создал метод, который проверяет соседей каждый раз, когда вы его вызываете, а затем рекурсивно проходит по массиву. См. этот ответ, который имеет начало точка для вашего проекта.   -  person Yahya    schedule 13.06.2017
comment
Дубликаты решают более сложную версию этой проблемы, но здесь можно использовать те же подходы. Аналогично Количество групп/островов 1 в a Матрица: уточнение определения.   -  person Bernhard Barker    schedule 13.06.2017
comment
@Dukeling Спасибо! Я искал несколько вещей, но так и не нашел их.   -  person andsec    schedule 13.06.2017

Ответы (1)


arrow_upward
0
arrow_downward

Вот грубый способ решения проблемы. Вы должны попытаться улучшить это, хотя.

public static void removeCloud(int x, int y, int[][] sky) {
    sky[x][y] = 0;
    if(x > 0 && sky[x-1][y] == 1) {
        removeCloud(x-1,y,sky);
    ...
}

public static int countClouds(int[][] sky) {
    int count = 0
    for(int i = 0; i < sky.length; i++) {
        for(int j = 0; j < sky[i].length) {
            if(sky[i][j] == 1) {
                count++;
                removeCloud(i,j,sky);
            }
        }
    }
}
person E.D.    schedule 13.06.2017