37. 跳马

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', () => {
    const [m,n] = lines[0].split(' ').map(Number);
    const board = [];
    const horses = [];
    for(let i=1; i<=m; i++) {
        const line = lines[i];
        board.push(line.split(''));
        line.split('').forEach((cell, j) => {
            if (cell !== '.') {
                horses.push({x: i-1, y: j, steps: parseInt(cell)});
            }
        })
    }
    console.log(bfs(m, n, horses));
});
function bfs(m, n, horses) {
    const directions = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1,2], [2,1], [2,-1], [1,-2]];
    let minSteps = Infinity;
    for(let i=0; i<m; i++) {
        for(let j=0; j<n; j++) {
            let steps = 0;
            let possible = true;
            for(const horse of horses) {
                const queue = [{x:horse.x, y:horse.y, step:0}];
                const visited = new Set([`${horse.x},${horse.y}`]);
                let found = false;
                while(queue.length > 0 && possible) {
                    const {x,y,step} = queue.shift();
                    if (x===i&&y===j) {
                        steps += step;
                        found = true;
                        break;
                    }
                    for(const [dx,dy] of directions) {
                        const nx = x+dx;
                        const ny = y+dy;
                        if (nx>=0 && nx<m && ny>=0 && ny<n && step < horse.steps && !visited.has(`${nx},${ny}`)) {
                            queue.push({x:nx, y:ny, step: step+1});
                            visited.add(`${nx},${ny}`);
                        }
                    }
                }
                if (!found) {
                    possible = false;
                }
            }
            if(possible) {
                minSteps = Math.min(minSteps, steps);
            }
        }
    }
    return minSteps === Infinity ? -1 : minSteps;
}