どう書く?org#8053「島の数をカウントする」
お題
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
回答
object Q8053 { object Tile extends Enumeration { val White, Black, Fill = Value } import Tile._ def countIsland(str : String, target : Value) = { var data = parse(str) var result = 0 for (y <- 0 to data.length - 1; x <- 0 to data(y).length - 1) { if (data(y)(x) == target) { fill(data, y, x, target) result += 1 } } result } def parse(str : String) = { str.lines.toList.map(_.toList.map( x => if (x == '□') White else Black).toArray).toArray } def fill(data : Array[Array[Value]], y :Int, x :Int, target : Value):Unit = { if (y < 0 || y >= data.length || x < 0 || x >= data(y).length || data(y)(x) != target) { return } data(y)(x) = Fill fill(data, y-1, x, target) fill(data, y+1, x, target) fill(data, y, x-1, target) fill(data, y, x+1, target) } } object Main { val sample1 = """□■■□ |□□■□ |□■□□ |□■■□""".stripMargin val sample2 = """□□□□ |■□■□ |□■□□ |□□□□""".stripMargin def main(args : Array[String]) = { println(Q8053 countIsland(sample1, Q8053.Tile.White)) // 2 println(Q8053 countIsland(sample1, Q8053.Tile.Black)) // 2 println(Q8053 countIsland(sample2, Q8053.Tile.White)) // 1 println(Q8053 countIsland(sample2, Q8053.Tile.Black)) // 3 } }
すごくjavaっぽいです…。
完全に副作用無しで書こうして挫折した。
こういうのを関数型言語っぽく書くにはどうしたらいいんだろう。