結果
| 問題 |
No.179 塗り分け
|
| ユーザー |
 tanson
|
| 提出日時 | 2025-08-19 00:36:52 |
| 言語 | Standard ML (MLton 20210117) |
| 結果 |
AC
|
| 実行時間 | 604 ms / 3,000 ms |
| コード長 | 6,246 bytes |
| コンパイル時間 | 3,725 ms |
| コンパイル使用メモリ | 687,224 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-08-19 00:36:59 |
| 合計ジャッジ時間 | 6,369 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 40 |
ソースコード
fun readInt () =
valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn)
fun readStr () =
valOf (TextIO.inputLine TextIO.stdIn)
fun readNewline () =
TextIO.inputLine TextIO.stdIn
val () =
let
val h = readInt ()
val w = readInt ()
val _ = readNewline ()
fun makeGrid () =
let
val s_s = List.tabulate (h, fn _ => (readStr ()))
val grid = Array.tabulate (h, fn _ => Array.array (w, false))
val blacks = ref []
val y = ref 0
in
(
List.app
(fn s =>
let
val line = String.explode s
val x = ref 0
in
(
List.app
(fn c =>
(
if c = #"#" then
(
Array.update (Array.sub (grid, !y), !x, true);
blacks := (!x, !y) :: !blacks
)
else ignore ();
x := !x + 1
)
)
line;
y := !y + 1
)
end
)
s_s;
blacks := List.rev (!blacks);
(grid, !blacks)
)
end
val (originalGrid, originalBlacks) = makeGrid ()
fun satisfy dx dy =
let
val used = Array.tabulate (h, fn _ => Array.array (w, false))
val blacks = ref originalBlacks
val satisfied = ref true
val need_loop = ref true
in
(
while !need_loop do
let
val (x, y) = List.hd (!blacks)
in
(
blacks := List.tl (!blacks);
if Array.sub (Array.sub (used, y), x)
then
(
ignore ()
)
else
(
let
val xx = x + dx
val yy = y + dy
in
if 0 <= xx andalso
xx < w andalso
0 <= yy andalso
yy < h andalso
Array.sub (Array.sub (originalGrid, yy), xx) andalso
Array.sub (Array.sub (used, yy), xx) = false
then
(
Array.update (Array.sub (used, y), x, true);
Array.update (Array.sub (used, yy), xx, true)
)
else
(
need_loop := false;
satisfied := false
)
end
);
if List.length (!blacks) = 0 then need_loop := false
else ignore ()
)
end;
!satisfied
)
end
fun canPainted () =
let
val dy = ref 0
val satisfied = ref false
val need_loop_y = ref true
in
(
while !need_loop_y do
let
val dx = ref (if !dy = 0 then 0 else (~w) + 1)
val need_loop_x = ref true
in
(
while !need_loop_x do
if ((!dx = 0 andalso !dy = 0) = false) andalso
(satisfy (!dx) (!dy))
then
(
satisfied := true;
need_loop_y := false;
need_loop_x := false
)
else
(
dx := !dx + 1;
if w <= !dx then need_loop_x := false
else ignore ()
);
if !need_loop_y
then
(
dy := !dy + 1;
if h <= !dy then need_loop_y := false
else ignore ()
)
else ignore ()
)
end;
!satisfied
)
end
in
if List.length originalBlacks = 0 then print "NO\n"
else if canPainted () then print "YES\n"
else print "NO\n"
end