結果

問題 No.13 囲みたい！
コンテスト
ユーザー te-sh
提出日時 2016-09-01 13:33:30
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,644 bytes
コンパイル時間 843 ms
コンパイル使用メモリ 122,120 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 04:05:36
合計ジャッジ時間 1,410 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std.algorithm, std.array, std.container, std.range, std.bitmanip;
import std.numeric, std.math, std.bigint, std.random;
import std.string, std.conv, std.stdio, std.typecons;

struct point {
  int x;
  int y;

  point opBinary(string op)(point rhs) {
    static if (op == "+") return point(x + rhs.x, y + rhs.y);
    else static if (op == "-") return point(x - rhs.x, y - rhs.y);
  }
}

const auto sibPoints = [point(-1, 0), point(0, -1), point(1, 0), point(0, 1)];

struct currPrev {
  point curr;
  point prev;
}

void main()
{
  auto rd = readln.split.map!(to!int);
  auto w = rd[0], h = rd[1];
  auto mij = iota(h).map!(_ => readln.split.map!(to!int).array).array;

  writeln(calc(h, w, mij) ? "possible" : "impossible");
}

bool calc(int h, int w, int[][] mij)
{
  auto visited = new bool[][](h, w);
  foreach (i; 0..h) {
    foreach (j; 0..w) {
      if (!visited[i][j]) {
        auto r = calcN(i, j, h, w, mij, visited);
        if (r) return true;
      }
    }
  }
  return false;
}

bool calcN(int i, int j, int h, int w, int[][] mij, ref bool[][] visited)
{
  bool valid(point p) {
    return p.x >= 0 && p.x < w && p.y >= 0 && p.y < h;
  }

  auto stack = SList!currPrev();
  stack.insertFront(currPrev(point(j, i), point(-1, -1)));
  while (!stack.empty) {
    auto s = stack.front, cp = s.curr, pp = s.prev;
    stack.removeFront;

    foreach (sib; sibPoints) {
      auto np = cp + sib;

      if (!valid(np) || mij[np.y][np.x] != mij[cp.y][cp.x] || np == pp) continue;
      if (visited[np.y][np.x]) return true;

      stack.insertFront(currPrev(np, cp));
      visited[np.y][np.x] = true;
    }
  }

  return false;
}
0