「霧島京子の挑戦状」A*アルゴリズムをJavaScriptで実装した。

kyokoKirishima.js

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf8');
let line = '';
process.stdin.on('data', chunk =>  {
  line += chunk;
});

process.stdin.on('end', () => {
  const str = getInput(line),
    hwn = str[0].split(' ').map(e => parseInt(e)),
    h = hwn[0], w = hwn[1], n = hwn[2],
    g = str.slice(1, h + 1).map(e => e.split('')),
    s = str[h + 1].split(' ').map(e => parseInt(e)),
    t = str[h + 2].split(' ').map(e => parseInt(e));
  let openList = [],
    memo = [...Array(h)].map(e => [...Array(w)].map(el => null));

  //printMap(g);
  //スタート地点のノードを作成し、状態をNoneからOpenにする
  let sp = new Node(s[0], s[1], 'Open', 0, getHeuristicCost(s[0], s[1], t[0], t[1]));
  sp.setScore(sp.cost + sp.heuristicCost);
  //スタート地点のノードをmemoする
  memo[sp.y - 1][sp.x - 1] = sp;
  //周りをOpenする
  openList = openList.concat(openPoint(sp.x, sp.y, w, h, t, g, sp, memo));
  //周りをOpenしたノードをCloseする
  sp.status = 'Closed';
  //Openした座標をmemoに追加する
  openList.forEach(e => {
    memo[e.y - 1][e.x - 1] = e;
  });

  while(memo[t[1] - 1][t[0] - 1] === null){
    //基準ノードの判定
    let baseNode = getMinimumScore(openList);
    //OpenListからClosedのノードを削除する
    openList = openList.filter(e => e.status !== 'Closed');
    //基準ノードの周りをOpenする
    openList = openList.concat(openPoint(baseNode.x, baseNode.y, w, h, t, g, baseNode, memo));
    //周りをOpenしたノードをCloseする
    baseNode.status = 'Closed';
    //Openした座標をmemoに追加する
    openList.forEach(e => {
      memo[e.y - 1][e.x - 1] = e;
    });
  }
  let route = getParent(memo[t[1] -1][t[0] - 1]).reverse().map(e => [e.x, e.y]);
  convertRoute(route).forEach(e => {
    console.log(e);
  });
});

function getInput(str){
  return str.split(/\r\n|\r|\n/).slice(0, -1);
}

//地図の二次元配列から特定の地点の内容を返す
function getPoint(x, y, g){
  return g[y - 1][x - 1];
}

//テスト用に地図を表示する関数
function printMap(g){
  console.log(g.map(e => e.reduce((a, b) => a + b)));
}

//推定コストを求める関数
//x,yは現在の座標
//g_x,g_yはゴールの座標
function getHeuristicCost(x, y, g_x, g_y){
  return Math.abs(g_x - x) + Math.abs(g_y - y)
}

//隣のノードに移動する際にかかる実際のコストを求める関数
//x,yは移動先のノード座標
//gは地図の配列
function getCost(x, y, g, node){
  const p = getPoint(x, y, g),
    trap = /[A-Z]/,
    key = /[a-z]/,
    notEnterable = /#/,
    enterable = /\./;
  if(trap.test(p)){
    //罠解除鍵を所持している場合は1,所持していない場合は100
    if(key.test(node.keys)){
      return 1;
    }else{
      return 100;
    }
  }else if(key.test(p)){
    return 1;
  }else if(notEnterable.test(p)){
    return null;
  }else if(enterable.test(p)){
    return 1;
  }
  return null;
}

//その座標が地図内であるか、進入可能な座標であるかを判断する
function isEnterable(x, y, w, h, g, node){
  const xmtz = x - 1 >= 0,
    xltw = x - 1 < w,
    ymtz = y - 1 >= 0,
    ylth = y - 1 < h,
    all = xmtz && xltw && ymtz && ylth;
  let enterablePoint = false;
  if(all){
    enterablePoint = getCost(x, y, g, node) !== null;
  }
  return all && enterablePoint ? true : false;
}

//上下左右の座標をOpenする関数
function openPoint(x, y, w, h, t, g, parent, memo){
  //上下左右の座標
  const point = [
    [x - 1, y],  //左
    [x + 1, y],  //右
    [x, y - 1],  //上
    [x, y + 1]]; //下
  let arr = [];
  point.forEach(e => {
    if(isEnterable(e[0], e[1], w, h, g, parent)){
      //memoに存在しなければノードをOpenする
      if(memo[e[1] - 1][e[0] - 1] === null){
        let node = new Node(e[0], e[1], 'Open', getCost(e[0], e[1], g, parent), getHeuristicCost(e[0], e[1], t[0], t[1]))
        node.setScore(node.cost + node.heuristicCost);
        node.setParent(parent);
        //罠解除鍵をノードに追加する処理
        if(/[a-z]/.test(getPoint(node.x, node.y, g))){
          node.addKeys(getPoint(node.x, node.y, g));
        }
        node.addKeys(parent.keys);
        arr.push(node);
      }
    }
  });
  return arr;
}

//OpenListからscoreが最も小さいノードを返す関数
function getMinimumScore(list){
  return list.sort((a, b) => {
    if(a.score < b.score) return -1;
    if(a.score > b.score) return 1;
    return 0;
  })[0];
}

//Nodeから再起的にparentを取得する関数
function getParent(node, arr = []){
  arr.push(node);
  if(node.parent === null) return arr;
  return getParent(node.parent, arr);
}

//ルートをUDLRに変換する関数
function convertRoute(arr){
  let result = [];
  for(let i = 0; i < arr.length - 1; i++){
    let x = arr[i][0] - arr[i + 1][0],
      y = arr[i][1] - arr[i + 1][1];
    if(x === 0 && y === 1) result.push('U');
    if(x === 0 && y === -1) result.push('D');
    if(x === 1 && y === 0) result.push('L');
    if(x === -1 && y === 0) result.push('R');
  }
  return result;
}
//通過可能なノードを表すオブジェクト
class Node {
  constructor(x, y, status, cost, heuristicCost){
    this.x = x;
    this.y = y;
    this.status = status;
    this.cost = cost;
    this.score = 0;
    this.heuristicCost = heuristicCost;
    this.parent = null;
    this.keys = '';
  }

  setParent(parent){
    this.parent = parent;
  }

  setScore(score){
    this.score = score;
  }

  addKeys(key){
    this.keys += key;
  }
}