Рекурсия с возвратом, похожая на игру «Сапер», двумерный логический массив

В основном это домашнее задание, и если вы ответите на мой вопрос, я предпочитаю получить наводку на ответ, а не код и сам ответ.

Это должен быть рекурсивный метод, который в заданном двумерном логическом массиве должен возвращать количество истинных зон в массиве — количество строк и столбцов в массиве всегда будет одинаковым.

Истинная зона определяется, когда есть хотя бы один истинный элемент, если у него есть соседний другой элемент, который также является истинным, они все равно считаются как 1. Элементы, расположенные по диагонали, не считаются соседними.

Например, в этой матрице, когда 1 соответствует истине, а 0 — ложному, есть 3 истинных зоны — две ячейки слева, три ячейки справа и одна ячейка в последней строке, отдельно от него. .

1 0 0 1
1 0 1 1
0 1 0 0

Я не знаю, как подойти к этой проблеме рекурсивно, в простой итерации это было бы довольно просто, я полагаю, но кажется невозможным проверить массив с помощью метода, который вызывает сам себя.

У кого-нибудь есть зацепка?


java arrays recursion boolean minesweeper
person Ohande    schedule 29.12.2020    source источник
comment
рекурсия не откатывается. иногда вычислительная структура с возвратом строится с помощью рекурсии - например, создание n вложенных циклов с помощью рекурсии для выполнения рекурсивного -возврат; но рекурсия - это вещь в себе. здесь есть естественно рекурсивное решение. что касается возврата назад, то есть повторной попытки после неудачи до успеха, я не вижу, что здесь нужно повторять. вы просто разделяете вещь на две части, подсчитываете интересующий вас вопрос в каждой (или в одной?), затем складываете две вещи вместе, возможно, корректируя счет.   -  person Will Ness    schedule 29.12.2020
comment
поэтому, если вы настаиваете на рекурсивном возврате решения, у меня нет на это ответа .   -  person Will Ness    schedule 29.12.2020
comment
@WillNess спасибо за ответ. Мне не требуется решение для поиска с возвратом, я просто подумал, что, поскольку это было последнее, что мы изучали, это должен быть ответ, но это не обязательно.   -  person Ohande    schedule 30.12.2020
comment
попробуйте разбить его на первую строку и остальные строки. создайте две вещи для остальных строк - количество и активные точки поверх второй строки, каким-то образом. затем объедините это с первой строкой и создайте новый счет и новые активные точки поверх первой строки. это смутное представление о том, как это можно было бы сделать. Я думаю, что ответ судьи также намекает на это, но я не понимаю, почему он говорит как о вертикальном, так и о горизонтальном разделении (или я неправильно понял это).   -  person Will Ness    schedule 30.12.2020

Ответы (3)


arrow_upward
1
arrow_downward

По сути, это связанные компоненты, используйте DFS.

person Andrew Vershinin    schedule 29.12.2020
comment
ваша ссылка описывает итеративный алгоритм, а не рекурсивный: в любом случае поиск, начинающийся с некоторой конкретной вершины v, перед возвратом найдет весь компонент, содержащий v (и не более). Чтобы найти все компоненты графа, выполните цикл [выделено мной --wn] по его вершинам, начиная новый поиск в ширину или в глубину всякий раз, когда цикл достигает вершины. который еще не был включен в ранее найденный компонент. - person Will Ness; 29.12.2020
comment
@WillNess Да, но основной алгоритм рекурсивный, задача не говорит, что они вообще не могут использовать циклы. Или я ошибаюсь? - person Andrew Vershinin; 30.12.2020
comment
@AndrewVershinin Да, я не упоминал об этом, но я вообще не могу использовать циклы, ни в самом методе, ни в любых других методах, касающихся ответа. - person Ohande; 30.12.2020

arrow_upward
1
arrow_downward

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

// spoiler alert 

















































public class Minefield {
  public static void main(String[] args) throws Exception {
    int[][] field = { //
        { 1, 0, 0, 1 }, //
        { 1, 0, 1, 1 }, //
        { 0, 1, 0, 0 }, //
    };
    int w = field[0].length;
    int h = field.length;

    int count = count(0, 0, w, h, true, field, new int[h][w]);
    System.out.println("true zones: " + count);
  }

  private static int count(int x, int y, int w, int h, boolean checkForNewZone /* false: mark zone */, int[][] field, int[][] marked) {
    if(x < 0 || x >= w || y < 0 || y >= h) {
      return /* out of bounds */ 0;
    }

    if(checkForNewZone) {
      int count = 0;
      if(field[y][x] == 1 && marked[y][x] == 0) {
        // a new true zone -> count it
        count++;
        // and mark it
        count(x, y, w, h, false, field, marked);
      }

      // iterate to the next field
      // x++;
      // if(x >= w) {
      //   x = 0;
      //   y++;
      // }
      // count += count(x, y, w, h, true, field, marked);

      // check neighboring fields (right & down should cover everything, assuming the starting point is the top left)
      count += count(x + 1, y, w, h, true, field, marked);
      count += count(x, y + 1, w, h, true, field, marked);
      return count;
    }
    else {
      // mark zone
      if(field[y][x] == 1 && marked[y][x] == 0) {
        marked[y][x] = 1;
        count(x + 1, y, w, h, false, field, marked);
        count(x - 1, y, w, h, false, field, marked);
        count(x, y + 1, w, h, false, field, marked);
        count(x, y - 1, w, h, false, field, marked);
      }

      return 0;
    }
  }
}
person Reto Höhener    schedule 29.12.2020
comment
зачем имитировать итерацию, когда есть естественно рекурсивный алгоритм, а OP запрашивает его? - person Will Ness; 29.12.2020
comment
Нет причин. Это было лучшее, что я мог сделать. Мне также интересно увидеть естественное решение, чтобы извлечь из него уроки. - person Reto Höhener; 29.12.2020
comment
как следует из приведенного выше ответа, нам просто нужно найти естественный способ каким-то образом разбить эту проблему на части, решить каждую / одну из этих частей, а затем найти способ объединить результаты обратно. мое текущее ощущение состоит в том, что это должно быть возможно путем разделения строки и остальных; решение каждого (большая часть рекурсивно); затем объединение результатов. комбинация, конечно, не просто сложение двух счетов. - person Will Ness; 29.12.2020
comment
этот ответ, однако, предполагает два плевка AFAICT, один отделяет строку, а другой - столбец, и я не понимаю, почему это должно быть так или что делать с ними обоими одновременно. (выше в хронологическом порядке, я почти всегда использую этот порядок на SO) - person Will Ness; 29.12.2020
comment
Я отредактировал более «растущий» алгоритм вместо линейной «итерации». Это теперь «настоящий» рекурсивный алгоритм? - person Reto Höhener; 29.12.2020
comment
Java слишком многословна для меня, извините. :) но если, учитывая n строк, вы решаете (n-1) строк рекурсивно, а затем каким-то образом получаете окончательный результат из этого рекурсивного подрезультата и первой строки, тогда да, это будет настоящий рекурсивное решение. - person Will Ness; 29.12.2020

arrow_upward
0
arrow_downward

Типичные рекурсивные алгоритмы состоят из двух частей:

  1. базовый случай
  2. индуктивный шаг

Начните с определения базовых случаев. Скорее всего, они будут идентифицированы по размеру входного массива. Например, массив 0x0 не имеет настоящих зон. Иногда существует несколько базовых вариантов.

Затем определите, как, учитывая ответ на меньшую версию входных данных, вы можете вычислить ответ на большую версию входных данных. Это может выглядеть как переход от массива nxm с количеством зон Z к массиву (n+1)xm с зонами Z' и массиву nx(m+1) с зонами Z''. Часто для достижения успеха необходимо решить немного более сложную задачу, потому что вы можете предположить больше об ответе на меньший вход.

Обычно эти два случая довольно легко перевести в рекурсивную программу.

person Judge Mental    schedule 29.12.2020
comment
зачем идти в двух направлениях, когда все, что вам нужно, это одно, а идти в двух направлениях сложно и никуда не ведет? но общий совет здравый; нам просто нужно определить, как разделить проблему и как объединить результаты обратно... и в этом весь вопрос. - person Will Ness; 29.12.2020