私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「画像から連結成分の数を求めよう」（CodeIQ）を参照してください。
あなたは食品メーカーに勤めており、画像認識で商品を検査することで業務を省力化するよう求められました。
画像認識はDeep Learningが得意とする分野ですが、まず「隗より始めよ」ということで、画像から物体の数を求めるプログラムの開発に着手することにしました。
本設問で求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、ドット(.)とゼロ(0)の２文字で構成された文字列が同文字数複数行送られる。
入力は１文字を1ピクセル、1行分の文字列を横一列とした２値画像とみなす。
この時横軸、縦軸とも長さは4以上20以下とする。
ゼロ(0)が上下左右斜めの8方向に連結した領域（連結成分）の数を求め、その数を標準出力に返すこと。
なお領域外のピクセルは、ドット(.)とみなすこと。
以下、入力と出力例です。
入力 出力 .0..
00..
....
...0
2 .0..
00..
..0.
...0
1
いかがでしょうか？
一見単純に見える連結成分の取得ですが、効率的に処理しようとすると奥が深いことに気づかされると思います。
それでは、是非挑戦してみてくださいね。
【問題】
標準入力から、ドット(.)とゼロ(0)の２文字で構成された文字列が同文字数複数行送られます。
この入力を２値画像とみなし、ゼロが上下左右斜めの8方向に連結した領域（連結成分）の数を求め、その数を標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
$Map = nil
def search(inputs, now, cnt)
dir = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]]
queue = [now]
while !queue.empty?
pos = queue.pop
for d in dir
nxt = [pos[0] + d[0], pos[1] + d[1]]
next if (nxt[0] < 0) || (nxt[1] < 0) || (nxt[0] >= inputs.size) || (nxt[1] >= inputs[0].size)
next if inputs[nxt[0]][nxt[1]] == '.'
if $Map[nxt[0]][nxt[1]] != 0 then next
else
$Map[nxt[0]][nxt[1]] = cnt
queue.push(nxt)
end
end
end
end
def solve(inputs)
cnt = 0
for r in 0...inputs.size
for c in 0...inputs[0].size
if inputs[r][c] == '0' then
if $Map[r][c] == 0 then
cnt += 1
$Map[r][c] = cnt
search(inputs, [r, c], cnt)
end
end
end
end
return cnt
end
# main
inputs = []
while line = gets
line.strip!
inputs << line
end
$Map = Array.new(inputs.size){Array.new(inputs[0].size, 0)}
p solve(inputs)
「連接成分」が何か知らなかったので調べました。
★★★ですがやや簡単な気がします。
入力値を1行ずつ配列inputsにとります。Rubyの文字列は[]で配列のようにアクセスできるので配列にする必要はありません。
$Mapは記録領域で、inputsと同じサイズの0埋めされた二次元配列として準備します。
入力値の最初から最後まで順に0の場所を探し、その場所の$Mapの値が0ならsearch()で連結成分を探します。
cntは連結成分の数でsearch()で探索が必要になる毎に+1します。これによって終了時のcntの値が答えになります。
連結成分を探します。
inputsは入力値の配列です。
nowはスタート地点の座標です。
cntは$Mapに書き込む値です。
dirは隣接領域の相対座標です。
queueにスタート地点nowをセットし、queueが空になるまでループします。
dirの各方向をチェックし、inputsの座標が0でなければ無視します。領域外も無視します。
＄Mapの当該座標が0以外なら探索済みなので無視します。
$Mapの当該座標が0なら$Mapの当該座標にcntをセットし、queueにも追加します。
queueが空になった時点で$Mapの連結成分の座標にcntの値が書き込まれた状態になります。
この問題はなかなか面白かったと思います。入力値の最大が20*20と小さいのでこれで十分ですがもっと巨大なデータの場合、これで十分なのかな？
ちなみに、連結成分の意味を知らなかったので調べたら、深さ優先探索云々という文言があったので深さ優先で探索しましたが、queueをpopするかshiftするだけの差なので幅優先でも同じ結果になるような気がします。