Submission #4015922

Source Code Expand

Copy
"use strict";

function _toConsumableArray(arr) { return _arrayWithoutHoles(arr) || _iterableToArray(arr) || _nonIterableSpread(); }

function _nonIterableSpread() { throw new TypeError("Invalid attempt to spread non-iterable instance"); }

function _iterableToArray(iter) { if (Symbol.iterator in Object(iter) || Object.prototype.toString.call(iter) === "[object Arguments]") return Array.from(iter); }

function _arrayWithoutHoles(arr) { if (Array.isArray(arr)) { for (var i = 0, arr2 = new Array(arr.length); i < arr.length; i++) { arr2[i] = arr[i]; } return arr2; } }

function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _nonIterableRest(); }

function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance"); }

function _iterableToArrayLimit(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

function main(input) {
  // 標準入力を行ごとに分解
  var lines = input.split("\n"); // HとWを受け取る

  var _lines$0$match$slice$ = lines[0].match(/^(\d+)\s+(\d+)$/).slice(1).map(function (i) {
    return parseInt(i, 10);
  }),
      _lines$0$match$slice$2 = _slicedToArray(_lines$0$match$slice$, 2),
      H = _lines$0$match$slice$2[0],
      W = _lines$0$match$slice$2[1]; // Sたちを取り出す


  var S = lines.slice(1, H + 1); // 各マスを既に訪れたかどうかを記録する2次元配列を作成

  var visited = Array.from({
    length: H
  }, function (x) {
    return new Array(W).fill(false);
  }); // 各連結成分を深さ優先探索

  var result = 0;

  for (var x = 0; x < W; x++) {
    for (var y = 0; y < H; y++) {
      // 再帰関数を呼び出す
      var _runRecursive = runRecursive(search, x, y),
          _runRecursive2 = _slicedToArray(_runRecursive, 2),
          black = _runRecursive2[0],
          white = _runRecursive2[1];

      result += black * white;
    }
  } // 答えを出力


  console.log(result);

  function* search(x, y) {
    if (visited[y][x]) {
      // このマスは探索済みだ
      return [0, 0];
    }

    visited[y][x] = true;
    var black = 0,
        white = 0; // 現在の位置をカウント

    var here = S[y][x];

    if (here === "#") {
      black++;
    } else {
      white++;
    } // 上下左右を探索


    var _arr2 = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    for (var _i2 = 0; _i2 < _arr2.length; _i2++) {
      var _arr2$_i = _slicedToArray(_arr2[_i2], 2),
          dx = _arr2$_i[0],
          dy = _arr2$_i[1];

      var nextx = x + dx,
          nexty = y + dy;

      if (nextx < 0 || nexty < 0 || nextx >= W || nexty >= H) {
        continue;
      } // 隣が自分と異なる場合のみ探索可能


      if (S[nexty][nextx] !== here) {
        // 再帰呼出しはyieldで行う
        var _ref = yield [nextx, nexty],
            _ref2 = _slicedToArray(_ref, 2),
            b = _ref2[0],
            w = _ref2[1];

        black += b;
        white += w;
      }
    }

    return [black, white];
  }
} // 標準入力を文字列で受け取ってmain関数を実行


main(require("fs").readFileSync("/dev/stdin", "utf8"));

function runRecursive(func) {
  // 最終結果を受け取るオブジェクトを用意
  var rootCaller = {
    lastReturnValue: null
  }; // 自前のコールスタックを用意

  var callStack = []; // 最初の関数呼び出しを追加

  for (var _len = arguments.length, args = new Array(_len > 1 ? _len - 1 : 0), _key = 1; _key < _len; _key++) {
    args[_key - 1] = arguments[_key];
  }

  callStack.push({
    iterator: func.apply(void 0, args),
    lastReturnValue: null,
    caller: rootCaller
  });

  while (callStack.length > 0) {
    var stackFrame = callStack[callStack.length - 1];
    var iterator = stackFrame.iterator,
        lastReturnValue = stackFrame.lastReturnValue,
        caller = stackFrame.caller; // 関数の実行を再開

    var _iterator$next = iterator.next(lastReturnValue),
        value = _iterator$next.value,
        done = _iterator$next.done;

    if (done) {
      // 関数がreturnしたので親に返り値を記録
      caller.lastReturnValue = value;
      callStack.pop();
    } else {
      // 関数がyieldした(valueは再帰呼び出しの引数リスト)
      callStack.push({
        iterator: func.apply(void 0, _toConsumableArray(value)),
        lastReturnValue: null,
        caller: stackFrame
      });
    }
  }

  return rootCaller.lastReturnValue;
}

Submission Info

Submission Time
Task C - Alternating Path
User uhyo_
Language JavaScript (node.js v5.12)
Score 300
Code Size 5040 Byte
Status
Exec Time 1398 ms
Memory 134544 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 300 / 300 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01.txt 375 ms 28808 KB
02.txt 357 ms 16008 KB
03.txt 69 ms 10308 KB
04.txt 235 ms 15760 KB
05.txt 1398 ms 134544 KB
06.txt 1090 ms 90060 KB
07.txt 927 ms 80908 KB
08.txt 378 ms 24440 KB
09.txt 418 ms 27004 KB
10.txt 55 ms 7372 KB
11.txt 58 ms 7628 KB
12.txt 59 ms 7756 KB
sample-01.txt 57 ms 7372 KB
sample-02.txt 57 ms 7372 KB
sample-03.txt 57 ms 7372 KB