#15/20 DFS: Connected Cell in a Grid [Cracking the Coding Interview Challenges]

#15 DFS: Connected Cell in a Grid

www.hackerrank.com

以下のような入力が与えられる。

4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0

1行目にn行、2行目にm列、それ以降はn行m列分のマトリックスがスペース区切りで与えられる。 マトリックス内で、1のセルが隣接している(縦横斜め)領域を調べ、マトリックス内での最大領域数を出力する。

上記入力の場合、1が隣接している最大領域は5となるので、5を出力する。

5

solution

再帰ありDFS(depth first search)で解いた。以下、rubyでの解。

一度訪問した箇所を再度調べる必要はないので、訪問済みの位置には0をセットしている。

#!/bin/ruby

class Solution

    def initialize(matrix)
        @matrix = matrix
    end

    def getBiggestResion
        matrix = @matrix.clone
        maxSize = 0

        for row in 0..(matrix.size - 1)
            for column in 0..(matrix[row].size - 1)
                if matrix[row][column] == 1
                    size = getResionSize(matrix, row, column)
                    maxSize = size if maxSize < size
                end
            end
        end
        return maxSize
    end
    
    private
        def getResionSize(matrix, row, column)
            return 0 if row < 0 || column < 0 || row >= matrix.size || column >= matrix[row].size
            return 0 if matrix[row][column] == 0

            size, matrix[row][column] = 1, 0
            for r in (row - 1)..(row + 1)
                for c in (column - 1)..(column + 1)
                    if r != row || c != column
                        size += getResionSize(matrix, r, c)
                    end
                end
            end
            return size
        end
end

input = $stdin.read.split("\n")
n, m, matrix = input.shift.to_i, input.shift.to_i, []
input.each_with_index { |v, i| matrix[i] = v.split(" ").map(&:to_i) }
puts (Solution.new(matrix)).getBiggestResion

github.com

DFS(depth-first search: 深さ優先探索)とは

深さ優先探索 - Wikipedia

まとめ

スタックでやる再帰なしより、再帰で書く方が楽だと思う。