本履歴

購入した古本の履歴と時々プログラミング

Cracking the Code Interview 16.19 Pond Sizes

もう1題は深さ優先探索の練習問題。長方形の区画の高さ情報(0は水面)が与えられるので全ての池を求めるというもの。池は上下左右斜めで繋がっているという定義。深さ優先探索再帰で書くと簡単だけど、たまにスタックがいっぱいになったりするので注意が必要。いつも思うのは、チェック先セルが範囲内かをチェックするのにRangeを使っているけど遅い気がするんだよなあ。不等号の方が速いはず。Ruby配列には範囲外を指定するとnilが返る仕様なんだけど、多次元だとnil[4]とかでmethod missingエラーになって処理が美しくないんだよね。Nilクラスにメソッド追加してnil返すようにすればいいんだけど。まあ、周りを壁で囲えば気にしなくていいんだけど、配列操作がRubyは非常に面倒くさいのでやりたくないしindex -1で最後にアクセスできるので、与えられる配列の最後に2つ番兵入れるだけだけどね。不等号と言えば、Enumerable#minも2値の場合は遅いと思う。ループの最深では不等号にしないとTLE。せっかく短く書けるからRuby使っているのに、冗長な書き方しないといけないのは本末転倒なんだけど。時間制限がある場合はしようがない。

def pond_sizes(pond)
    def dfs(x,y,pond)
        ret = 1
        pond[x][y]=-1
        [[1,0],[0,1],[-1,0],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]].each{|dx,dy|
            nx,ny = x+dx, y+dy
            next unless (0...pond.size)===nx
            next unless (0...pond.first.size)===ny
            ret += dfs(nx,ny,pond) if pond[nx][ny]==0
        }
        ret
    end

    h=pond.size
    w=pond.first.size
    ret=[]
    h.times{|i|w.times{|j|ret << dfs(i,j,pond) if pond[i][j]==0}}
    ret
end

if __FILE__==$0
    #text example
    pond=[[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]]
    p pond_sizes(pond) #=> [2,4,1]
    
    pond =[[0]]
    p pond_sizes(pond) #=> [1]

    pond =[[1,0]*50,[0,1]*50]
    p pond_sizes(pond) #=> [100]
end