题目描述

blablabla

样例

blablabla

算法1

bfs

时间复杂度

O(n)

javascript 代码

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

async function getData() {
    return new Promise((resolve, reject) => {
        const lines = [];
        rl.on('line', (line) => {
            lines.push(line);
        });
        rl.on('close', () => resolve(lines));
    });
}

async function main() {
    const lines = await getData();

    const nums = [];
    for (let i=0; i<lines.length; i++) {
        nums.push(lines[i].split(' '));
    }

    let queue = [];
    for (let i=0; i<nums.length; i++) {
        for (let j=0; j<nums[i].length; j++) {
            if (nums[i][j] === '2') {
                queue.push({ x: i, y: j, t: 0});
            }
        }
    }

    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];

    let max = -1;

    while (queue.length) {
        const item = queue.shift();
        if (item.t > max) {
            max = item.t;
        }

        for (let i=0; i<4; i++) {
            const x = item.x + dx[i];
            const y = item.y + dy[i];

            if (x >= 0 && x < nums.length && y >=0 && y< nums[0].length && nums[x][y] === '1') {
                queue.push({ x, y, t: item.t + 1});
                nums[x][y] = '2';
            }
        }
    }
    for (let i=0; i<nums.length; i++) {
        for (let j=0; j<nums[i].length; j++) {
            if (nums[i][j] === '1') {
                console.log(-1);
                return;
            }
        }
    }
    console.log(max);
}

main();