function solution(board) {

    const minCost = board.map((row) => row.map((i) => Infinity));
    minCost[0][0] = 0;

    const isSafe = (x,y) => !board[y] ? false : board[y][x]===0 ? true : false;

    const stack = [];
    const start = [[1,0],[0,1]];
    start.forEach((point,i) => isSafe(...point) && stack.push([...point, i, 100]));

    while(stack.length){
				const vertex = stack.shift();
        const [x,y,dir,cost] = vertex;

        if(cost <= minCost[y][x]){
            minCost[y][x] = cost;

            const right = [x+1, y, 0 ];
            const left = [x-1, y, 0 ];
            const top = [x, y-1, 1 ];
            const bottom = [x,y+1, 1 ];
            
            if(dir){
                isSafe(...top) && stack.push([ ...top, cost+100]);
                isSafe(...bottom) && stack.push([ ...bottom, cost+100]);
                isSafe(...left) && stack.push([ ...left, cost+600]);
                isSafe(...right) && stack.push([ ...right,cost+600]);   
            }else{
                isSafe(...left) && stack.push([...left, cost+100]);
                isSafe(...right) && stack.push([...right, cost+100]);
                isSafe(...top) && stack.push([...top, cost+600]);
                isSafe(...bottom) && stack.push([ ...bottom, cost+600]);
            }
        }
    }
    return minCost[board.length-1][board.length-1];
}

function solution(board) {
  const isSafe = (x, y) =>
    !board[y] ? false : board[y][x] === 0 ? true : false;

  const memo = board.map((row) => row.map((i) => Infinity));
  memo[0][0] = 0;

  const moves = [1, 1, -1, -1]; // 우 하 좌 상

  const stack = [];

  [[1,0],[0,1]].forEach(
    (point, dir) => isSafe(...point) && stack.push([dir, ...point, 100])
		// dir이 1이면 수직, 0이면 수평 방향
  );

  while (stack.length) {
    const [dir, x, y, cost] = stack.shift();

    if (cost <= memo[y][x]) {
      memo[y][x] = cost;

      moves.forEach((move, i) => {
        const nextDir= i % 2; // 1이면 수직, 0이면 수평
        const nextPoint = nextDir ? [x, y + move] : [x + move, y];

        isSafe(...newPoint) && 
            (nextDir===dir 
            ? stack.push([nextDir, ...nextPoint , cost+100])
            : stack.push([nextDir, ...nextPoint, cost+600]));
      });
    }

  }

  return memo[board.length - 1][board.length - 1];
}

function solution(board) {
  const isSafe = (x, y) =>
    !board[y] ? false : board[y][x] === 0 ? true : false;

  const memo = board.map((row) => row.map((i) => Infinity));
  memo[0][0] = 0;

  const moves = [1, 1, -1, -1]; // 우 하 좌 상

  const stack = [];

  [[1,0],[0,1]].forEach(
    (point, dir) => isSafe(...point) && stack.push([dir, ...point, 100])
  );

  while (stack.length) {
    const [dir, x, y, cost] = stack.shift();

    const minCharge = [];
    const maxCharge = [];

    if (cost <= memo[y][x]) {
      memo[y][x] = cost;

      moves.forEach((move, i) => {
        const nextDir = i % 2;
        const nextPoint = nextDir ? [x, y + move] : [x + move, y];

        isSafe(...nextPoint) && 
            (dir===nextDir 
             ? minCharge.push([nextDir, ...nextPoint, cost + 100]) 
             : maxCharge.push([nextDir, ...nextPoint, cost + 600]));
      });
    }

    stack.push(...minCharge, ...maxCharge);
  }

  return memo[board.length - 1][board.length - 1];
}

function solution(board) {

    const minCost = board.map((row) => row.map((i) => [Infinity, Infinity]));
    minCost[0][0] = [0,0];

    const isSafe = (x,y) => !board[y] ? false : board[y][x]===0 ? true : false;

    const dxdy = [
        [[1,-1,0,0],[0,0,1,-1]],
        [[0,0,1,-1],[1,-1,0,0]]
    ];
    
    const stack = [];
    [[1,0],[0,1]].forEach((start,i) => isSafe(...start) && stack.push([...start, i,i, 100]));

    while(stack.length){
        const [x,y,startDir,dir,cost] = stack.shift();

        if(cost <= minCost[y][x][startDir]){
            minCost[y][x][startDir] = cost;
            
            for(let i=0; i<4; i++){
                const xx = x + dxdy[dir][0][i];
                const yy = y + dxdy[dir][1][i];
                isSafe(xx, yy) && stack.push([xx, yy, startDir, xx === x ? 1 : 0, cost + (i<2 ? 100 : 600)]);
            }
        }
    }
    return Math.min(...minCost[board.length-1][board.length-1]);
}

int[][] board = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 1, 0, 0},
        {1, 0, 0, 0, 1},
        {0, 1, 1, 0, 0}
    };
[[0,0,0,0,0],[0,1,1,1,0],[0,0,1,0,0],[1,0,0,0,1],[0,1,1,0,0]];

function solution(board) {

    const minCost = board.map((row) => row.map((i) => [Infinity, Infinity]));
    minCost[0][0] = [0,0];

    const isSafe = (x,y) => !board[y] ? false : board[y][x]===0 ? true : false;

    const dxdy = [
        [[1,-1,0,0],[0,0,1,-1]],
        [[0,0,1,-1],[1,-1,0,0]]
    ];
    
    const stack = [];
    [[1,0],[0,1]].forEach((start,i) => isSafe(...start) && stack.push([...start, i ,i, 100]));

    while(stack.length){
        const [x,y,startDir,dir,cost] = stack.shift();

        if(cost < minCost[y][x][startDir]){
            minCost[y][x][startDir] = cost;
            
            for(let i=0; i<4; i++){
                const dx = dxdy[Math.abs(dir)][0][i];
                const dy = dxdy[Math.abs(dir)][1][i];
                const xx = x + dx;
                const yy = y + dy;
                const nextDir = dx > 0 ? 0 : dx < 0 ? '0' : dy;
                if(dir!==nextDir && dir + nextDir==0){ // 반대방향 이동
                    continue;
                }
                
                isSafe(xx, yy) && stack.push([xx, yy, startDir, nextDir, cost + (i<2 ? 100 : 600)]);
            }
        }
    }
    return Math.min(...minCost[board.length-1][board.length-1]);
}