結果
問題 | No.13 囲みたい! |
ユーザー | te-sh |
提出日時 | 2017-05-09 10:19:42 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 2,251 bytes |
コンパイル時間 | 888 ms |
コンパイル使用メモリ | 112,504 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-03 13:12:24 |
合計ジャッジ時間 | 2,018 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 5 ms
4,384 KB |
testcase_04 | AC | 3 ms
4,384 KB |
testcase_05 | AC | 8 ms
4,380 KB |
testcase_06 | AC | 3 ms
4,384 KB |
testcase_07 | AC | 8 ms
4,384 KB |
testcase_08 | AC | 9 ms
4,384 KB |
testcase_09 | AC | 8 ms
4,380 KB |
testcase_10 | AC | 3 ms
4,384 KB |
testcase_11 | AC | 7 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,380 KB |
testcase_14 | AC | 4 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,380 KB |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; import std.container; // SList, DList, BinaryHeap void main() { auto rd = readln.split.to!(size_t[]), w = rd[0], h = rd[1]; auto mij = Grid!(int, int)(h.iota.map!(_ => readln.split.to!(int[])).array); auto vij = Grid!(bool, int)(h, w); bool wfs(point s) { auto q = SList!pointsCP(pointsCP(s, point(-1, -1))); vij[s] = true; while (!q.empty) { auto cp = q.front; q.removeFront; auto curr = cp.curr, prev = cp.prev; foreach (np; mij.sibPoints4(curr)) { if (np != prev && mij[curr] == mij[np]) { if (vij[np]) return true; vij[np] = true; q.insertFront(pointsCP(np, curr)); } } } return false; } bool calc() { foreach (p; vij.points) if (!vij[p] && wfs(p)) return true; return false; } writeln(calc ? "possible" : "impossible"); } struct pointsCP { point curr; point prev; } struct Point(T) { T x, y; point opBinary(string op)(point rhs) { static if (op == "+") return point(x + rhs.x, y + rhs.y); } } alias Point!int point; struct Grid(T, U) { import std.algorithm, std.conv, std.range, std.traits, std.typecons; const sibs4 = [Point!U(-1, 0), Point!U(0, -1), Point!U(1, 0), Point!U(0, 1)]; T[][] m; const size_t rows, cols; mixin Proxy!m; this(size_t r, size_t c) { rows = r; cols = c; m = new T[][](rows, cols); } this(T[][] s) { rows = s.length; cols = s[0].length; m = s; } pure auto dup() const { return Grid(m.map!(r => r.dup).array); } pure auto opIndex(Point!U p) const { return m[p.y][p.x]; } pure auto opIndex(size_t y) { return m[y]; } pure auto opIndex(size_t y, size_t x) const { return m[y][x]; } static if (isAssignable!T) { auto opIndexAssign(T v, Point!U p) { return m[p.y][p.x] = v; } auto opIndexAssign(T v, size_t y, size_t x) { return m[y][x] = v; } } pure auto validPoint(Point!U p) const { return p.x >= 0 && p.x < cols && p.y >= 0 && p.y < rows; } pure auto points() const { return rows.to!U.iota.map!(y => cols.to!U.iota.map!(x => Point!U(x, y))).joiner; } pure auto sibPoints4(Point!U p) const { return sibs4.map!(s => p + s).filter!(p => validPoint(p)); } }