結果
問題 | No.13 囲みたい! |
ユーザー | te-sh |
提出日時 | 2017-02-17 16:01:50 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 2,072 bytes |
コンパイル時間 | 723 ms |
コンパイル使用メモリ | 103,264 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-03 01:34:31 |
合計ジャッジ時間 | 1,707 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 4 ms
4,380 KB |
testcase_04 | AC | 3 ms
4,376 KB |
testcase_05 | AC | 6 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 6 ms
4,376 KB |
testcase_08 | AC | 6 ms
4,376 KB |
testcase_09 | AC | 6 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 5 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,376 KB |
testcase_14 | AC | 3 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,376 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 = Matrix!int(h.iota.map!(_ => readln.split.to!(int[])).array); auto vij = Matrix!bool(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 (sp; sibPoints) { auto np = curr + sp; if (mij.validIndex(np) && 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!int) 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; const auto sibPoints = [point(-1, 0), point(0, -1), point(1, 0), point(0, 1)]; struct Matrix(T) { import std.algorithm, std.conv, std.range, std.traits, std.typecons; T[][] m; 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; } auto opIndex(U)(U p) { static if (is(U == Point!V, V)) return m[p.y][p.x]; else return m[p]; } auto opIndex(size_t y, size_t x) { return m[y][x]; } static if (isAssignable!T) { auto opIndexAssign(U)(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; } } auto validIndex(U)(Point!U p) { return p.x >= 0 && p.x < cols && p.y >= 0 && p.y < rows; } auto points(U)() { return rows.to!U.iota.map!(y => cols.to!U.iota.map!(x => Point!U(x, y))).joiner; } }