スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

どう書く?org F#  島の数をカウントする

どう書く?org F#  島の数をカウントする
 
「どう書く?org」http://ja.doukaku.org/に挑戦3問目です。 
さて今回の問題は次のような内容。 
 
(問題) 
島の数をカウントするhttp://ja.doukaku.org/219/
 
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。
 
ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。
 
例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ
 
例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
 
今回はとにかくDiscriminated unionを使うの巻です。
 
type Color =
    |White
    |Black
 
type Piece =
    | Island of Color * Option <int>
    | Dummy
 
としておきます。
 
島を配列で例えば
 
[| [|0;1;1;0|];
   [|0;0;1;0|];
   [|0;1;0;0|];
   [|0;1;1;0|] |]
表します。
 
これをmakeUpArray関数で
 
 [|[|Dummy; Dummy; Dummy; Dummy; Dummy; Dummy|];
    [|Dummy; Island (White,null); Island (Black,null); Island (Black,null);Island (White,null); Dummy|];
    [|Dummy; Island (White,null); Island (White,null); Island (Black,null);Island (White,null); Dummy|];
    [|Dummy; Island (White,null); Island (Black,null); Island (White,null);Island (White,null); Dummy|];
    [|Dummy; Island (White,null); Island (Black,null); Island (Black,null);Island (White,null); Dummy|];
    [|Dummy; Dummy; Dummy; Dummy; Dummy; Dummy|]|]
と変換します。Dummyで取り囲むわけです。(nullはNoneとして表示されています)
 
あとはこれで、一つ取り出してはそれがIsland(_,None)のときは、島番号をつけます(これは色別にインクリメントしていく)
その後
上下左右の場所にあるものを順番に取り出し、同色でIsland(_,None)のときは、先ほどの島番号をつけます、更に、この場合は、その上下左右それぞれの島を取り出し....というように再帰的に定義します。
 
コードは以下の通りです。
 
type Color =
    |White
    |Black
 
type Piece =
    | Island of Color * Option <int>
    | Dummy
    //結果表示用
    member this.toStr () =
        match this with
        | Island (White,Some(n)) -> sprintf "[W%d]" n
        | Island (Black,Some(n)) -> sprintf "[B%d]" n
        | _ -> "    "
             
 
let makeUpArr (rawArr : int [][]) =
    let tempArr = [| for i in 0 .. (Array.length rawArr) + 1 do
                            yield (Array.create (Array.length rawArr.[0] + 2)) Dummy|]
        
    for i in 0 .. (Array.length rawArr) - 1 do
        let t = rawArr.[i]
        for j in 0 .. (Array.length rawArr.[0])-1 do
            if rawArr.[i].[j] = 0 then
                tempArr.[i+1].[j+1] <- Island(White,None)
            else 
                tempArr.[i+1].[j+1] <- Island(Black,None)
            
    tempArr
    
//色別のカウンター
let mutable WhiteCount =  0
let mutable BlackCount =  0
 
let rec nearCheck (i0,j0) (arr: Piece [] [] ) =
    for (v1,v2) in [(1,0);(-1,0);(0,1);(0,-1)] do
        let (i1,j1) = (i0 + v1,j0 + v2) 
        match arr.[i0].[j0] ,arr.[i1].[j1] with
        |Island (c1,Some(number)),Island(c2,None) when c1 = c2 -> arr.[i1].[j1] <- Island(c1,Some(number));nearCheck(i1,j1) arr
        | _ -> ()
 
let check i j (arr: Piece [] [] ) =
    match arr.[i].[j] with
    |Island(c1,None) ->match c1 with
                       | White -> WhiteCount <- WhiteCount + 1; arr.[i].[j] <- Island (White,Some(WhiteCount))
                       | Black -> BlackCount <- BlackCount + 1; arr.[i].[j] <- Island (Black,Some(BlackCount))
                       nearCheck (i,j) arr
    | _ -> () 
   
let cope (arr : Piece [] []) =
 
    WhiteCount <- 0
    BlackCount <- 0
 
    for i = 1 to (Array.length arr - 2) do
        for j = 1 to (Array.length arr.[i] - 2) do
            check i j arr 
 
let dispResult (arr : Piece [] []) =
    printfn ""
    printfn "白の島は%dつ" WhiteCount
    printfn "黒の島は%dつ" BlackCount
    
    for i = 0 to (Array.length arr - 1) do
        for j = 0 to (Array.length arr.[i] - 1) do
            printf "%s" (arr.[i].[j].toStr()) 
        printf "\n"
 
let solve (rawArr : int [] [] ) =
    let data = makeUpArr rawArr
    cope data
    dispResult data
 
solve [| [|0;1;1;0|];[|0;0;1;0|];[|0;1;0;0|];[|0;1;1;0|] |]
solve [| [|0;0;0;0|];[|1;0;1;0|];[|0;1;0;0|];[|0;0;0;0|] |]
 
実行例
 
 
白の島は2つ
黒の島は2つ
                        
    [W1][B1][B1][W2]    
    [W1][W1][B1][W2]    
    [W1][B2][W2][W2]    
    [W1][B2][B2][W2]    
                        
 
白の島は1つ
黒の島は3つ
                        
    [W1][W1][W1][W1]    
    [B1][W1][B2][W1]    
    [W1][B3][W1][W1]    
    [W1][W1][W1][W1]    
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。