사라지는 발판

const check = (board, x, y) => {
  return (
    x >= 0 &&
    y >= 0 &&
    x < board.length &&
    y < board[0].length &&
    board[x][y] !== 0
  );
};

const directions = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

function solution(board, aloc, bloc) {
  const playA = (depth, a, b, board) => {
    const [ax, ay] = a;
    const [bx, by] = b;

    const nowBoard = JSON.parse(JSON.stringify(board));

    const winCaseDepths = [];
    const loseCaseDepths = [];

    for (const [dx, dy] of directions) {
      const nx = ax + dx;
      const ny = ay + dy;

      if (check(nowBoard, nx, ny)) {
        nowBoard[ax][ay] = 0;

        const result = playB(depth + 1, [nx, ny], [bx, by], nowBoard);
        (result.winner === 'A' ? winCaseDepths : loseCaseDepths).push(result);
      }
    }

    if (
      (winCaseDepths.length || loseCaseDepths.length) &&
      ax === bx &&
      ay == by
    ) {
      return {
        winner: 'A',
        depth: depth + 1,
      };
    }

    if (winCaseDepths.length) {
      return {
        winner: 'A',
        depth: Math.min(...winCaseDepths.map((v) => v.depth)),
      };
    } else if (loseCaseDepths.length) {
      return {
        winner: 'B',
        depth: Math.max(...loseCaseDepths.map((v) => v.depth)),
      };
    } else {
      return {
        winner: 'B',
        depth,
      };
    }
  };

  const playB = (depth, a, b, board) => {
    const [ax, ay] = a;
    const [bx, by] = b;

    const nowBoard = JSON.parse(JSON.stringify(board));

    const winCaseDepths = [];
    const loseCaseDepths = [];

    for (const [dx, dy] of directions) {
      const nx = bx + dx;
      const ny = by + dy;

      if (check(nowBoard, nx, ny)) {
        nowBoard[bx][by] = 0;

        const result = playA(depth + 1, [ax, ay], [nx, ny], nowBoard);
        (result.winner === 'B' ? winCaseDepths : loseCaseDepths).push(result);
      }
    }

    if (
      (winCaseDepths.length || loseCaseDepths.length) &&
      ax === bx &&
      ay == by
    ) {
      return {
        winner: 'B',
        depth: depth + 1,
      };
    }

    if (winCaseDepths.length) {
      return {
        winner: 'B',
        depth: Math.min(...winCaseDepths.map((v) => v.depth)),
      };
    } else if (loseCaseDepths.length) {
      return {
        winner: 'A',
        depth: Math.max(...loseCaseDepths.map((v) => v.depth)),
      };
    } else {
      return {
        winner: 'A',
        depth,
      };
    }
  };

  const result = playA(0, aloc, bloc, board);

  return result.depth;
}

function solution(board, aloc, bloc) {
    const R = board.length;
    const C = board[0].length;
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    const checkRange = (x, y) => {
        if(x >= 0 && x < R && y >= 0 && y < C){
            return true;
        }
        
        return false;
    }
    
    const canMove = (x, y) => {
        for(let i = 0; i < 4; i++){
            let nx = x + dx[i];
            let ny = y + dy[i];
            
            if(checkRange(nx, ny) && board[nx][ny]){
                return true;
            }
        }
        
        return false;
    }
    
    const dfs = (ax, ay, bx, by) => {
        const result = [false, 0];
        
        if(!canMove(ax, ay)){
            return result;
        }
        
        if(board[ax][ay]){
            let currentMin = Infinity;
            let currentMax = -Infinity;
            
            for(let i = 0; i < 4; i++){
                const nextAX = ax + dx[i];
                const nextAY = ay + dy[i];
                
                if(!checkRange(nextAX, nextAY) || !board[nextAX][nextAY]){
                    continue;
                }
                
                board[ax][ay] = 0;
                const tmp = dfs(bx, by, nextAX, nextAY);
                board[ax][ay] = 1;
                
                if(!tmp[0]){
                    result[0] = true;
                    currentMin = Math.min(currentMin, tmp[1]);
                } else if(!result[0]){
                    currentMax = Math.max(currentMax, tmp[1]);
                }
            }
            
            result[1] = result[0] ? currentMin + 1 : currentMax + 1;
        }

        return result;
    }
    
    return dfs(aloc[0], aloc[1], bloc[0], bloc[1])[1];
}