Untitled
unknown
javascript
6 months ago
2.6 kB
1
Indexable
Never
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;