js задача на рекурсию

Question

Всем привет, не могу уже неделю решить задачу, просто не могу придумать алгоритм.

Имеется карта размером NxN, в каждой клетке которой указана высота данной точки на местности. Данная карта окружена бесконечным рвом. Определить конфигурацию луж после бесконечного дождя. По диагонали вода стекать не может. Входные данные: файл input.txt. На первой строке файла записано число N. Далее следует N строк, содержащих числа высоты через пробел (от 0 до 9)

Код для получения данных из файла, и формирование двух исходных массивов

const fs = require('fs');

const fileContent = fs.readFileSync('input.txt', 'utf8').split('\r\n');
const length = +fileContent[0];
const field = fileContent.slice(1).map(row => row.split(' '));
const fallout = [];

function init() {
    for (let i = 0; i < length; i++) {
        fallout[i] = [];
        for (let j = 0; j < length; j++) {
            field[i][j] = +field[i][j];
            fallout[i][j] = 'X';
        }
    }
}

init();

Входные данные

6
6 3 4 5 6 7
5 2 1 3 2 8
3 1 1 5 6 5
7 5 5 3 1 7
8 1 1 6 2 6
7 1 5 8 6 5

Answer 1

Рекурсия (для решения этой задачи) не нужна.

Нам потребуется три двумерных массива: высота рельефа, высота на которой будет находиться вода, и атрибут указывающий что высота воды для клетки уже известна.

Для каждой клетки: высота воды в клетке равна меньшей из двух величин: (1) высота рельефа в данной клетке и (2) минимальная высота воды в сопредельных клетках.

В начальный момент вы знаете уровень воды в клетках на границе (он равен рельефу местности, поскольку с приграничных клеток вода переливается в ров).

Составляете список клеток (Б), в которых высота воды еще не известна, но которые граничат с клетками с известной высотой воды. В клетках из списка Б, уровень воды не может быть ниже чем уровень рельефа местности в этой точке, и не выше чем высота воды на сопредельных клетках, где уровень известен, если этот уровень выше высоты рельефа. Выбираем клетку из списка Б, клетку К где этот уровень минимален. (Понятно, что во всех оставшихся клетках высота воды не может быть ниже этого уровня, поэтому, когда высота во всех остальных соседях клетки К будет известна она не повлияет на высоту воды в точке К.) Вычислим уровень воды в точке К, обновим список Б. Повторяем пока высота воды не будет известна во всех точках.

Лужи останутся в клетках, где высота воды не совпадает с высотой рельефа.

Это самый медленный из возможных, но самый простой для понимания алгоритм. Возможно, он не пройдет систему тестирования по времени (для больших массивов).

Answer 2

Не уверен, что оптимальное решение, но все-таки решение:

const n = 6;
const map = [
  [6, 3, 4, 5, 6, 7],
  [5, 2, 1, 3, 2, 8],
  [3, 1, 1, 5, 6, 5],
  [7, 5, 5, 3, 1, 7],
  [8, 1, 1, 6, 2, 6],
  [7, 1, 5, 8, 6, 5]
];

let res = [];

// Функция проверяющая выход ко рву
function check(y, x, level, checked) {
  // Сохранение проверенных клеток
  checked.push(y * n + x);

  // Исключение клеток, примыкающих к краю
  if ((y % (n - 1)) * (x % (n - 1)) == 0) {
    return true;
  }

  // Проверка соседних клеток
  for (let i = y - 1; i <= y + 1; i++) {
    for (let j = x - 1; j <= x + 1; j++) {
      // Исключение проверенных клеток
      if (checked.indexOf(i * n + j) < 0) {
        // Проверка клеток по вертикали и горизонтали, высота которых ниже
        if ((i == y ^ j == x) && map[i][j] <= level) {
          // Если есть выход ко рву
          if (check(i, j, level, checked) == true) {
            return true;
          }
        }
      }
    }
  }

  // Выхода ко рву нет
  return false;
}

// Заполнение карты результатов
for (let i = 0; i < n; i++) {
  res.push([]);
  for (let j = 0; j < n; j++) {
    res[i].push(check(i, j, map[i][j], []) ? 'o' : 'x');
  }
}

// Вывод результата
for (let i = 0; i < n; i++) {
  console.log(i + "..... " + res[i].join(' '));
}

БЛОГ НА HUSL

js задача на рекурсию

Ответы (2 шт):