Ход коня (BFS алгоритм)

Question

Вопрос аналогичен в тему Задача о перемещении шахматного коня на доске , надо найти за сколько ходов конь переместится в указанные координаты.

Программа выдает не правильную цифру**

 function solution(x){
    var arr = ["a","b","c","d",'e',"f","g",'h']
    let dx = [2,2,-2,-2,1,1,-1,-1]
    let dy = [-1,1,1,-1,2,-2,2,-2]
    board = []
    for (var i = 0; i < 8; i++) {
        let tox = []
        board.push(tox)
        for (var j = 0; j < 8; j++) {
            board[i][j] = 0 // заполняем доску нулями
        }
    }
    var x1 = arr.indexOf(x[0][0].toLowerCase())+1 // координаты начальной позиции коня
    var x2 = Number(x[0][1])
    board[x1-1][x2-1] = 1;      //получить координаты и поставить на доске 1
    var y1 = arr.indexOf(x[1][0].toLowerCase())+1 // координаты конечной позиции
    var y2 = Number(x[1][1])
    let xod = []      //сделаные ходы
    let way = []
    //очередь которая содержит: текущие координаты, количество ходов, чтобы
    //добратся до даной клетки, и список всех проделаных ходов для вывода
    way.push([x1-1, x2-1],xod)     //добавляем в очередь текущее положение и никакой ход
    while(!way.length==0){      //пока очередь не пуста
        now = way[0]        //на какой клетке находимся сейчас
        xod = [way[0]]    //какие ходы были сделаны до этого
        if(now[0] == y1-1 && now[1] == y2-1) {break}   
        //если сейчас находимся на конечной клетке - выход из цикла
            way.pop();     // удалить текущий элемент
            for (let d = 0; d < 8; d++) {
            if(now[0]+dx[d] < 8 && now[0]+dx[d] >= 0 &&
                now[1]+dy[d] < 8 && now[1]+dy[d] >= 0 &&
                board[now[0]+dx[d]][now[1]+dy[d]] == 0){ 
                //если координаты не превышают 8 и не меньше 0, и на этой клетке ещё не был
                let xod2 = xod
                xod2.push([now[0]+dx[d], now[1]+dy[d]]);
                way.push([now[0]+dx[d], now[1]+dy[d]], xod2);
                //заталкиваем в очередь пару из новых координат и проделаных ходов
                board[now[0]+dx[d]][now[1]+dy[d]] = 1;
                //клетку отмечаем 1
            }               
        }
    } return xod.length   // Необходимое количество ходов
}
    console.log(solution(["D5","F1"]))//2
    console.log(solution(["D5","E3"]))//1
    console.log(solution(["C3","B5"]))//1
    console.log(solution(["D5","H7"]))//2

Answer 1

А вы не пробовали попробовать написать это на JavaScript, а не на Си?

В каждой шутке доля шутки

(function() {

    const MAX_STEPS = 3;
    const MAX_ROADS = 5;

    const copy = (area) => area.slice(0).map((line) => line.slice(0)); 
    const printArea = (arr) => [...arr].forEach((line) => console.log(line.join(' ') + '\n'));
    const arr = (m) => [...new Array(8)].reduce((acm) => [...acm, acm.length], []).map(m);
    const area = arr((i) => i % 2 === 0 ? arr(j => j % 2 === 0 ? 1 : 0) : arr(j => j % 2 === 0 ? 0 : 1));

    const inRange = (x,y) => {
      if (x < 0 || x > area.length) {
        return false;
      } else if (y < 0 || y > area[0].length) {
        return false;
      } else {
        return true;
      }
    };

    const step = (x,y) => [
      [x + 1, y - 2],
      [x + 2, y - 1],
      [x + 1, y + 2],
      [x + 2, y + 1],
      [x - 1, y - 2],
      [x - 2, y - 1],
      [x - 1, y + 2],
      [x - 2, y + 1]
    ].filter(([x, y]) => inRange(x,y))
    
    const draw = (steps = ["0:1", "2:2", "1:0"]) => steps
      .reduce((acm, cur) => [...acm, [steps[acm.length - 1], cur]], []).slice(1)
      .map((dots) => dots.map((d) => d.split(':').map((cell) => parseInt(cell))))
      .forEach(([from, to]) => {

        const way = copy(area);
        const [x1, y1] = from;
        const [x2, y2] = to;

        way[y1][x1] = 'x';
        way[y2][x2] = 'x';

        console.warn(`${x1} ${y1} => ${x2} ${y2}`);
        printArea(way);
      });

    const bfs = ({x1, y1}, {x2, y2}) => {

      const roads = [];

      const process = (dot = [x1, y1], ignore = new Set(), way = []) => {

          const [x, y] = dot;

          const n = `${x}:${y}`;
          ignore.add(n);
          way.push(n);

          if (x === x2 && y === y2) {
            roads.push(way);
            return;
          }

          if (way.length > MAX_STEPS) {
            return;
          }

          if (roads.length > MAX_ROADS) {
            return;
          }

          step(x, y)
            .filter(([x, y]) => !ignore.has(`${x}:${y}`))
            .forEach((cell) => process(cell, new Set([...ignore]), way.slice(0)));
      };

      process();

      return roads;
    };

    const roads = bfs({x1: 0, y1: 1}, {x2: 1, y2: 0}).sort((a, b) => a.length - b.length);
    const [road] = roads;
    draw(road);

})();

БЛОГ НА HUSL

Ход коня (BFS алгоритм)

Ответы (1 шт):