Prob D

by ipark

HTML

<h2>
Prob D. 
</h2>
<ul> 입력
  <li> 2
    <br>. .
    <br>* * </li>
  <li> 4
    <br>. . **
    <br>. * . .
    <br>* . . .
    <br>. . . . </li>
</ul>
<ul> 생성 결과
  <li> Expected: <span id="extected1">6</span>, Actual: <span id="actual1"></span> </li>
  <li> Expected: <span id="extected2">11</span>, Actual: <span id="actual2"></span> </li>
  <li> Expected: <span id="extected3">100</span>, Actual: <span id="actual3"></span> </li>
</ul>
<ul> 결과
  <li> Case1: <span id="result1"></span> </li>
  <li> Case2: <span id="result2"></span> </li>
  <li> Case3: <span id="result3"></span> </li>
</ul>

JavaScript

//-------------------------------------------------
// Utility Fn
//
function notNull(value) {
  return value !== null;
}

function enQueue(q, p) {
  var i, j, diff, node;

  for (i = 0; i < p.length; i++) {
    node = p[i];
    for (j = 0; j < q.length; j++) {
      diff = q[j];

      if (pMap[node.y][node.x] < pMap[diff.y][diff.x]) {
        q.splice(j, 0, node);
        break;
      }
    }

    if (j === q.length) {
      q.push(node);
    }
  }
}

function deQueue(q) {
  return q.shift();
}

function outOfMap(x, y) {
  return (x < 0 || y < 0 || goal < x || goal < y);
}

function comparer(l, r) {
  return (pMap[l.y][l.x] < pMap[r.y][r.x]) ? -1 : 1;
}

function makeMap(list) {
  var map = [];
  for (var i = 0; i < list.length; i++) {
    map.push(list[i].split('').map(Number));
  }
  return map;
}

function board(n, value) {
  var result = [];
  for (var i = 0; i < n; i++) {
    result.push(range(n, value));
  }
  return result;
}

function range(n, value) {
  var result = Array(n);
  for (var i = 0; i < n; i++) {
    result[i] = value;
  }
  return result;
}
//-------------------------------------------------
// Business Logic
//
function visit(x, y) {
  visited[y][x] = true;

  if (x === goal && y === goal) {
    return pMap[y][x];
  }

  var p = [left(x, y), up(x, y), right(x, y)].filter(notNull).sort(comparer);

  enQueue(promising, p);
  var next = deQueue(promising);

  return visit(next.x, next.y);
}

function left(prevX, prevY) {
  var x = prevX - 1,
      y = prevY;

  return getPromisingValue(prevX, prevY, x, y);
}

function up(prevX, prevY) {
  var x = prevX,
      y = prevY + 1;

  return getPromisingValue(prevX, prevY, x, y);
}

function right(prevX, prevY) {
  var x = prevX + 1,
      y = prevY;

  return getPromisingValue(prevX, prevY, x, y);
}

function getPromisingValue(prevX, prevY, x, y) {
  if (outOfMap(x, y) || visited[y][x]) return null;

  pMap[y][x] = pMap[prevY][prevX] + map[y][x];
  return {
    x: x,
    y: y
 ...