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;