17. 寻找最优的路测线路

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

const lines = [];
rl.on('line', (line) => {
    lines.push(line);
});
rl.on('close', () => {
    let R = parseInt(lines[0]);
    let C = parseInt(lines[1]);
    let Cov = [];
    for(let i=0; i<R; i++) {
        Cov.push(lines[i+2].split(' ').map(Number));
    }
    let minSignal = Math.min(...Cov.map(row => Math.min(...row)));
    let maxSignal = Math.max(...Cov.map(row => Math.max(...row)));
    console.log(search(Cov, minSignal, maxSianal));
})
class Cell {
    constructor(row, col) {
        this.row = row;
        this.col = col;
    }
}

function search(Cov, low, high) {
    while(low <= high) {
        let mid = Math.floor(low + (high - low)/2);
        if (bfs(Cov, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return high;
}
function bfs(Cov, minSignal) {
    let R = Cov.length;
    let C = Cov[0].length;
    if (Cov[0][0] < minSignal || Cov[R-1][C-1] < minSignal) {
        return false;
    }
    let visited = Array.from({length: R}, () => Array(C).fill(false));
    let queue = [];
    queue.push(new Cell(0, 0));
    visited[0][0] = true;

    let dr = [1, -1, 0, 0];
    let dc = [0, 0, 1, -1];
    while(queue.length) {
        let cell = queue.shift();
        if (cell.row === R-1 && cell.col === C-1) {
            return true;
        }
        for(let i=0; i<4; i++) {
            let nr = cell.row + dr[i];
            let nc = cell.col + dc[i];
            if (nr >0 && nr<R && nc>=0 && nc<C && !visited[nr][nc] && Cov[nr][nc] >= minSignal) {
                queue.push(new Cell(nr, nc));
                visited[nr][nc] = true;
            }
        }
    }
    return false;
}