Submission #4015744


Source Code Expand

Copy
"use strict";

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 _search = search(x, y),
          _search2 = _slicedToArray(_search, 2),
          black = _search2[0],
          white = _search2[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) {
        var _search3 = search(nextx, nexty),
            _search4 = _slicedToArray(_search3, 2),
            b = _search4[0],
            w = _search4[1];

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

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


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

Submission Info

Submission Time
Task C - Alternating Path
User uhyo_
Language JavaScript (node.js v5.12)
Score 0
Code Size 2982 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 0 / 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 240 ms 29052 KB
02.txt 97 ms 15868 KB
03.txt 62 ms 9360 KB
04.txt 89 ms 15860 KB
05.txt
06.txt
07.txt
08.txt 96 ms 16128 KB
09.txt 100 ms 16104 KB
10.txt 57 ms 7372 KB
11.txt 58 ms 7500 KB
12.txt 59 ms 7628 KB
sample-01.txt 57 ms 7372 KB
sample-02.txt 57 ms 7372 KB
sample-03.txt 57 ms 7372 KB