画像から連結成分の数を求めよう

画像から連結成分の数を求めよう

締め切りが 2018/02/02 10:00 AM なので，その 1 分後に投稿されるように予約

あなたは食品メーカーに勤めており、画像認識で商品を検査することで業務を省力化するよう求められました。

画像認識はDeep Learningが得意とする分野ですが、まず「隗より始めよ」ということで、画像から物体の数を求めるプログラムの開発に着手することにしました。

本設問で求められるプログラムの前提条件は、以下の通りとなります。

・ 標準入力から、ドット(.)とゼロ(0)の２文字で構成された文字列が同文字数複数行送られる。
・ 入力は１文字を1ピクセル、1行分の文字列を横一列とした２値画像とみなす。
・ この時横軸、縦軸とも長さは4以上20以下とする。
・ ゼロ(0)が上下左右斜めの8方向に連結した領域（連結成分）の数を求め、その数を標準出力に返すこと。
・ なお領域外のピクセルは、ドット(.)とみなすこと。

【問題】
標準入力から、ドット(.)とゼロ(0)の２文字で構成された文字列が同文字数複数行送られます。
この入力を２値画像とみなし、ゼロが上下左右斜めの8方向に連結した領域（連結成分）の数を求め、その数を標準出力に返してください。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

20×20 だと，地道にやっても R でも楽勝

f = function(s) {
    count = 0
    n = length(s)
    a = matrix(0, n+2, n+2)
    r = 1:n+1
    a[r, r] = sapply(s, function(t) unlist(strsplit(t, "")))
    repeat {
        # 新しい「島」の一端（"0" のセル）を探す
        found = FALSE
        for (i in r) {
            for (j in r) {
                if (a[i, j] == "0") {
                    found = TRUE
                    count = count+1
                    a[i, j] = "*" # あったら "*" にする
                    break
                }
            }
            if (found) {
                break
            }
        }
        if (!found) {
            break # "0" が 1 つもなかった（全て処理済み）ならば，終わり
        }
        # 1 つでもあれば，「島」を拡張する
        si = c(-1, 0, 1, -1, 1, -1, 0, 1)
        sj = c(-1,-1,-1,  0, 0,  1, 1, 1)
        repeat {
            replace = FALSE
            for (i in r) {
                for (j in r) {
                    if (a[i, j] == "*") { # "*" のセルの八方に "0" があれば
                        for (k in 1:8) {
                            if (a[i+si[k], j+sj[k]] == "0") {
                                a[i+si[k], j+sj[k]] = "*" # "*" に置き換える
                                replace = TRUE # 置き換えがあったことを記録
                            }
                        }
                    }
                }
            }
            if (!replace) { # 置き換えがなかったら「島」の拡張は終了
                for (i in r) {
                    for (j in r) {
                        if (a[i, j] == "*") {
                            a[i, j] = "." # 処理済みの「島」は「島」でないようにする
                        }
                    }
                }
                break
            }
        }
    }
    cat(count)
}

#f(readLines(file("stdin", "r")))

f(readLines("dat1")) # 2
f(readLines("dat2")) # 5
f(readLines("dat3")) # 7

dat1

00....
......
..000.
.00.0.
..000.
......

dat2

0....00.
0000000.
........
...0000.
..0....0
...0000.
........
.0.0..0.

dat3

....................
..000000............
.0..0..0....000000..
.0.....0....0....0..
.0000000....0.0..0..
............0.0.....
....00000...0.00000.
...00.......0.......
...0................
...0................
...0.....000........
....00..0...00......
.......00.....0.....
....................
...........000000...
.........00......00.
........0....000..0.
........0........00.
.........0000000000.
....................