Untitled

 avatar
unknown
javascript
2 years ago
2.6 kB
3
Indexable
function parking(ships) {
  // Сортируем корабли по убыванию количества ячеек формы
  ships.sort((a, b) => b.form.flat().reduce((sum, cell) => sum + cell, 0) - a.form.flat().reduce((sum, cell) => sum + cell, 0));

  const width = ships[0].form[0].length; // Ширина парковки
  const parkingLot = Array.from({ length: width }, () => Array(width).fill(null)); // Парковка (матрица)

  const result = [];

  for (const ship of ships) {
    let position = null;
    let isRotated = false;

    // Поиск свободного места для корабля
    for (let i = 0; i <= width - ship.form.length; i++) {
      for (let j = 0; j <= width - ship.form[0].length; j++) {
        if (canPark(ship, i, j)) {
          position = i;
          isRotated = false;
          break;
        } else if (canPark(ship, i, j, true)) {
          position = i;
          isRotated = true;
          break;
        }
      }
      if (position !== null) {
        break;
      }
    }

    // Парковка корабля на найденном месте
    parkShip(ship, position, isRotated);
    result.push({ shipId: ship.id, position: position + 1, isRotated });

    // Функция для проверки возможности парковки корабля на заданной позиции
    function canPark(ship, row, col, rotate = false) {
      const form = rotate ? rotateForm(ship.form) : ship.form;
      for (let i = 0; i < form.length; i++) {
        for (let j = 0; j < form[0].length; j++) {
          if (form[i][j] === 1 && parkingLot[row + i][col + j] !== null) {
            return false;
          }
        }
      }
      return true;
    }

    // Функция для поворота формы корабля
    function rotateForm(form) {
      const rotatedForm = Array.from({ length: form[0].length }, () => Array(form.length));
      for (let i = 0; i < form.length; i++) {
        for (let j = 0; j < form[0].length; j++) {
          rotatedForm[j][form.length - 1 - i] = form[i][j];
        }
      }
      return rotatedForm;
    }

    // Функция для парковки корабля на заданной позиции
    function parkShip(ship, row, col) {
      const form = isRotated ? rotateForm(ship.form) : ship.form;
      for (let i = 0; i < form.length; i++) {
        for (let j = 0; j < form[0].length; j++) {
          if (form[i][j] === 1) {
            parkingLot[row + i][col + j] = ship.id;
          }
        }
      }
    }
  }

  return result;
}

module.exports = parking;