#1113748 (Standard ML) No.179 塗り分け

• 問題: 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