#15 DFS: Connected Cell in a Grid
以下のような入力が与えられる。
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