結果

問題 No.13 囲みたい!
ユーザー vain0vain0
提出日時 2015-10-23 00:53:13
言語 F#
(.NET 7)
結果
TLE  
実行時間 -
コード長 2,327 bytes
コンパイル時間 5,105 ms
コンパイル使用メモリ 170,672 KB
実行使用メモリ 25,172 KB
最終ジャッジ日時 2023-09-30 05:05:56
合計ジャッジ時間 12,151 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
23,248 KB
testcase_01 AC 95 ms
25,064 KB
testcase_02 AC 98 ms
25,172 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) F# Compiler version 11.0.0.0 for F# 5.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

/home/judge/data/code/Main.fs(20,7): warning FS0025: Incomplete pattern matches on this expression. For example, the value '[|_; _; _|]' may indicate a case not covered by the pattern(s).

ソースコード

diff #

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