2i-barents-sea-pirates.js

/*

I. Пираты Баренцева моря

Ограничение времени	1 секунда (фактическое использование на тестах – до 73ms)
Ограничение памяти	64Mb (фактическое использование на тестах – до 8.27Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Вася играет в настольную игру «Пираты Баренцева моря», которая посвящена морским битвам. Игровое поле представляет собой квадрат из N×N клеток, на котором расположено N кораблей (каждый корабль занимает одну клетку).
Вася решил воспользоваться линейной тактикой, для этого ему необходимо выстроить все N кораблей в одном столбце. За один ход можно передвинуть один корабль в одну из четырёх соседних по стороне клеток. Номер столбца, в котором будут выстроены корабли, не важен. Определите минимальное количество ходов, необходимых для построения кораблей в одном столбце. В начале и процессе игры никакие два корабля не могут находиться в одной клетке.

Формат ввода
В первой строке входных данных задаётся число N (1 ≤ N ≤ 100).
В каждой из следующих N строк задаются координаты корабля: сначала номер строки, затем номер столбца (нумерация начинается с единицы).

Формат вывода
Выведите одно число — минимальное количество ходов, необходимое для построения.

Пример

Ввод
3
1 2
3 3
1 1

Вывод
3

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

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim().split('\n');

const zoneSize = parseInt(input[0]);

const zoneTemplate = new Array(zoneSize).fill(0).map(() => new Array(zoneSize).fill(false));

let colsCount = -1;
let colsArray = new Array(zoneSize);
let firstShipCol = zoneSize - 1;
let firstShipRow = zoneSize - 1;

for (let i = 1; i < input.length; ++i) {
    const coords = input[i].trim().split(' ');
    const row = parseInt(coords[0]) - 1;
    const col = parseInt(coords[1]) - 1;
    zoneTemplate[col][row] = true;

    if (col < firstShipCol) {
        firstShipCol = col;
    }
    if (row < firstShipRow) {
        firstShipRow = row;
    }

    ++colsCount;
    colsArray[colsCount] = col;
}

colsArray = colsArray.sort((a, b) => a - b);
const half = Math.floor(zoneSize / 2);
const median = zoneSize % 2 ? colsArray[half] : (colsArray[half - 1] + colsArray[half]) / 2;
const medianCols = median % 1 ? [Math.floor(median), Math.ceil(median)] : [median];

if (medianCols[0] > 0) {
    medianCols.unshift(medianCols[0] - 1);
}
if (medianCols[medianCols.length - 1] < zoneSize - 1) {
    medianCols.push(medianCols[medianCols.length - 1] + 1);
}

let bestResult = Infinity;

for (const targetCol of medianCols) {
    let zone = zoneTemplate;
    if (medianCols.length > 1) {
        zone = zoneTemplate.map((arr) => [...arr]);
    }

    let colFilled = 0;
    let rowUnchecked = 0;
    let moves = 0;

    targetRowLoop:
    for (let targetRow = 0; targetRow < zoneSize; ++targetRow) {
        if (zone[targetCol][targetRow] === true) {
            ++colFilled;
        } else {
            let row = targetRow;
            let colShift = 1;

            while (row >= rowUnchecked) {
                if (zone[targetCol + colShift]?.[row] === true) {
                    zone[targetCol + colShift][row] = false;
                    zone[targetCol][targetRow] = true;
                    moves += targetRow - row + colShift;
                    continue targetRowLoop;
                } else if (zone[targetCol - colShift]?.[row] === true) {
                    zone[targetCol - colShift][row] = false;
                    zone[targetCol][targetRow] = true;
                    moves += targetRow - row + colShift;
                    continue targetRowLoop;
                }
                --row;
            }

            while (row < zoneSize) {
                if (row > targetRow) {
                    colShift = 1;
                } else {
                    colShift = 2;
                }
                while (targetCol - colShift >= 0 || targetCol + colShift < zoneSize) {
                    if (zone[targetCol - colShift]?.[row] === true) {
                        zone[targetCol - colShift][row] = false;
                        zone[targetCol][targetRow] = true;
                        moves += Math.abs(targetRow - row) + colShift;
                        continue targetRowLoop;
                    } else if (zone[targetCol + colShift]?.[row] === true) {
                        zone[targetCol + colShift][row] = false;
                        zone[targetCol][targetRow] = true;
                        moves += Math.abs(targetRow - row) + colShift;
                        continue targetRowLoop;
                    }
                    ++colShift;
                }
                ++row;
                rowUnchecked = row;
            }
        }
    }
    bestResult = Math.min(bestResult, moves);
}

fs.writeFileSync('output.txt', `${bestResult}`);