Задача по олимпиадному программированию

Question

Наткнулся на одну задачу, я ее точно решить не смогу, но если кто-то ее решит, то был бы рад прийти в восторг от решения :)

Задача, как по мне, довольно сложная

Прочитал на одном форуме, что это нужно решать с помощью волнового обхода

В поисках сокровищ известный археолог попал в огромную сеть двумерных пещер. Он вспомнил, что в университете как раз делал дипломную работу по этой местности: руками подсчитывал количество сталактитов, сталагмитов и сталагнатов и записывал всё это в рабочую тетрадь. Да, ошибиться легко. Приходилось проверять себя несколько раз. Теперь же у него с собой есть портативный сканер местности, который переводит всё в матрицу из 0 и 1. Только вот незадача, там нет возможности узнать количество объектов на карте. Для знаменитого археолога нет непреодолимых препятствий, а проверить свои студенческие расчеты очень хочется.

Нужно реализовать метод scan, который принимает на вход карту – матрицу NxM, состоящую только из 1 (каменная порода) и 0 (пустое пространство). Матрица – это 2D карта пещеры, вид сбоку, аля платформер.

Пример карты:

[  
  [1, 1, 0, 0, 0, 1, 0, 1, 1],  
  [1, 1, 0, 1, 0, 1, 0, 0, 0],  
  [0, 1, 0, 1, 0, 0, 0, 1, 1]  
]

Формат вывода

Метод scan возвращает объект с количеством каждого типа образования {ceil: 0, ﬂoor: 0, both: 0}

Если образование свисает с потолка и не касается пола – ceil
Если образование растет от пола и не касается потолка – ﬂoor
Если образование свисает с потолка и при этом еще и касается пола – both Результат вывода на примере карты выше: {ceil: 2, ﬂoor: 2, both: 1}

Вот как стоило рассматривать массив, чтобы получить такой результат:

Примечания

У одного образования может быть несколько точек касания.

Пример 1:

[
  [1, 0, 1],
  [1, 1, 1],
  [0, 0, 0]
]

Результат: {ceil: 1, ﬂoor: 0, both: 0}

Пример 2:

[  
  [1, 0, 1],  
  [1, 1, 1],  
  [0, 0, 1]  
]

Результат: {ceil: 0, ﬂoor: 0, both: 1}

Считаем, что по диагонали образования не пересекаются:

[  
  [1, 0, 1],  
  [0, 1, 0],  
]

Результат: {ceil: 2, ﬂoor: 1, both: 0}

Answer 1

Ну так и используйте волновой алгоритм

const data = [
[  
  [1, 1, 0, 0, 0, 1, 0, 1, 1],  
  [1, 1, 0, 1, 0, 1, 0, 0, 0],  
  [0, 1, 0, 1, 0, 0, 0, 1, 1]  
],
[
  [1, 0, 1],
  [1, 1, 1],
  [0, 0, 0]
],
[  
  [1, 0, 1],  
  [1, 1, 1],  
  [0, 0, 1]  
],
[  
  [1, 0, 1],  
  [0, 1, 0],  
]
];

function buildPath(map, x, y, res) {
  // Если находимся за границей массива или
  // точку не нужно обрабатывать, то выходим
  if (
    y < 0 || y >= map.length ||
    x < 0 || x >= map[y].length ||
    map[y][x] !== 1
  )
    return;

  // Если на потолке
  if (y === 0)
    res.ceil = true;
  // Если на полу
  if (y === map.length - 1)
    res.floor = true;

  // Точку обработали
  map[y][x] = -1;

  // Проверяем соседние точки
  buildPath(map, x, y - 1, res);
  buildPath(map, x - 1, y, res);
  buildPath(map, x + 1, y, res);
  buildPath(map, x, y + 1, res);
}

function parse(map) {
  const res = {
    ceil: 0,
    floor: 0,
    both: 0
  };
  for (let i = 0; i < map[0].length; i++) {
    let testObj = {
      ceil: false,
      floor: false
    };
    // проверяем точку на потолке
    buildPath(map, i, 0, testObj);
    if (testObj.ceil) {  // если было касание потолка
      if (testObj.floor)  // и было касание пола
        res.both++;
      else
        res.ceil++;
    }
    
    testObj = {
      ceil: false,
      floor: false
    };
    // проверяем точку на полу
    buildPath(map, i, map.length - 1, testObj);
    if (testObj.floor) {  // если было касание пола
      if (testObj.ceil)  // и было касание потолка
        res.both++;
      else
        res.floor++;
    }
  }
  return res;
}

for (let i = 0; i < data.length; i++)
  console.log(parse(data[i]));

БЛОГ НА HUSL

Задача по олимпиадному программированию

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