結果

問題 No.13 囲みたい！
コンテスト
ユーザー vain0
提出日時 2015-10-23 00:53:13
言語 F#
(F# 4.0)
結果
TLE  
実行時間 -
コード長 2,327 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,966 ms
コンパイル使用メモリ 199,724 KB
実行使用メモリ 67,484 KB
最終ジャッジ日時 2024-07-22 23:02:27
合計ジャッジ時間 24,155 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (385 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.fs(20,7): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
raw source code 

open System
open System.Text
open System.Collections.Generic

module Str =
  let split (delim: string) (s: string) =
    s.Split ([| delim |], StringSplitOptions.RemoveEmptyEntries)

let neighbors8 = [(1, 0); (1, 1); (0, 1); (-1, 1); (-1, 0); (-1, -1); (0, -1); (1, -1)]

#if DEBUG
let inline err (s: string) = Console.Error.WriteLine s
#else
let inline err _ = ()
#endif

[<EntryPoint>]
let main argv =
  let s = Console.ReadLine ()
  let [| h; w |] = s |> Str.split " " |> Array.map (Int32.Parse)
  let board =
    [ for i in 0..(w - 1) do
        let s = Console.ReadLine ()
        yield s |> Str.split " " |> Array.map (Int32.Parse) |> List.ofArray
        ]
  let c_set = board |> List.concat |> Set.ofList

  let boardFromSet s =
    [ for i in 0..(w - 1) do
        for j in 0..(h - 1) do
          yield (if s |> Set.contains (i, j) then "*" else "_")
        yield "\r\n" ]
    |> List.fold (+) ""

  /// 色 c 以外の塗り潰し
  /// 淵に到達しなければ成功 (囲まれている)
  let rec dfs c visited (i, j) =
      if board.[i].[j] = c || visited |> Set.contains (i, j) then
        true
      else if not (1 <= i && i < w - 1 && 1 <= j && j < h - 1) then
        false
      else
        let visited = visited |> Set.add (i, j)
        List.forall id
          [ for (dx, dy) in neighbors8 ->
              dfs c visited (i + dx, j + dy)
              ]

  /// 四角があるパターン
  let k4 =
    List.exists id
      [ for i in 0..(w - 2) do
          for j in 0..(h - 2) do
            let b =
              List.forall id
                [ for (dx, dy) in [(0, 1); (1, 0); (1, 1)] do
                    yield board.[i].[j] = board.[i + dx].[j + dy]
                    ]
            //if b then err <| sprintf "四角 (%d, %d)" i j
            yield b
        ]
  /// 囲みがあるパターン
  let kN =
    List.exists id
      [ for i in 1..(w - 2) do
          for j in 1 ..(h - 2) do
            let b =
              List.exists id
                [ for c in c_set do
                    if c <> board.[i].[j] then
                      yield dfs c (Set.empty) (i, j) ]
            //if b then err <| sprintf "閉領域 (%d, %d)" i j
            yield b
            ]

  let result =
    (k4 || kN)
    
  printfn (if result then "possible" else "impossible")

  //exit code
  0
0