結果
問題 | No.179 塗り分け |
ユーザー |
|
提出日時 | 2017-02-08 14:27:34 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 15 ms / 3,000 ms |
コード長 | 1,503 bytes |
コンパイル時間 | 1,011 ms |
コンパイル使用メモリ | 105,088 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-12 06:58:58 |
合計ジャッジ時間 | 2,804 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 40 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; alias Point!int point; void main() { auto rd = readln.split.to!(int[]), h = rd[0], w = rd[1]; auto sij = h.iota.map!(_ => readln.chomp).array; auto s = { foreach (y; 0..h) foreach (x; 0..w) if (sij[y][x] == '#') return point(x, y); return point(-1, -1); }(); if (s == point(-1, -1)) { writeln("NO"); return; } auto canPaint(int x, int y) { auto d = point(x, y) - s; auto tij = new bool[][](h, w); tij[s.y][s.x] = tij[y][x] = true; foreach (iy; 0..h) foreach (ix; 0..w) if (sij[iy][ix] == '#' && !tij[iy][ix]) { auto ip = d + point(ix, iy); if (ip.x < 0 || ip.x >= w || ip.y >= h || sij[ip.y][ip.x] != '#' || tij[ip.y][ip.x]) return false; tij[iy][ix] = tij[ip.y][ip.x] = true; } return true; } auto r = { foreach (y; s.y..h) foreach (x; 0..w) if (s != point(x, y) && sij[y][x] == '#' && canPaint(x, y)) return true; return false; }(); writeln(r ? "YES" : "NO"); } struct Point(T) { T x, y; auto opBinary(string op: "+")(Point!T rhs) { return Point!T(x + rhs.x, y + rhs.y); } auto opBinary(string op: "-")(Point!T rhs) { return Point!T(x - rhs.x, y - rhs.y); } auto opBinary(string op: "*")(Point!T rhs) { return x * rhs.x + y * rhs.y; } auto opBinary(string op: "*")(T a) { return Point!T(x * a, y * a); } T hypot2() { return x ^^ 2 + y ^^ 2; } }