アルゴリズム書かなくていいので行数短くなるかなと思ったら、マップの制約を書くのに行数食ってしまうという罠。
問題
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
解答
キモとなる島の判定ロジックは、次のように書いてます。
fact islandLaw { all disj s,s': Square | s.island = s'.island iff s' in s.^{s1,s2: Square | (s2 in s1.(left+down) or s1 in s2.(left+down)) and s1.color = s2.color } }
要は「隣同士で色が同じになってるマスをずっと辿っていって、到達するマスは全部同じ島」ってことです。
以下は「仕様」全文。
one sig Answer { width, height, blackIslands, whiteIslands: Int } { blackIslands = #{x: Island | some g:Square | g.island = x and g.color = Black} whiteIslands = #{x: Island | some g:Square | g.island = x and g.color = White} } sig Square { row, col: Int, left, down: lone Square, color: Color, island: Island } abstract sig Color {} one sig White, Black extends Color {} sig Island {} fact islandLaw { all disj s,s': Square | s.island = s'.island iff s' in s.^{s1,s2: Square | (s2 in s1.(left+down) or s1 in s2.(left+down)) and s1.color = s2.color } } fact squareLaws { all s1, s2: Square | s1.row = s2.row and s1.col = s2.col iff s1 = s2 all g: Square { g.col = Answer.width - 1 => no g.left else g.left.row = g.row and g.left.col = g.col + 1 g.row = Answer.height - 1 => no g.down else g.down.row = g.row + 1 and g.down.col = g.col } } pred setSquare (r,c: Int, cl: Color) { some g: Square | g.row = r and g.col = c and g.color = cl } pred example1 () { Answer.width = 4 and Answer.height = 4 setSquare[0,0,White] and setSquare[0,1,Black] and setSquare[0,2,Black] and setSquare[0,3,White] setSquare[1,0,White] and setSquare[1,1,White] and setSquare[1,2,Black] and setSquare[1,3,White] setSquare[2,0,White] and setSquare[2,1,Black] and setSquare[2,2,White] and setSquare[2,3,White] setSquare[3,0,White] and setSquare[3,1,Black] and setSquare[3,2,Black] and setSquare[3,3,White] } run example1 for 16 pred example2 () { Answer.width = 4 and Answer.height = 4 setSquare[0,0,White] and setSquare[0,1,White] and setSquare[0,2,White] and setSquare[0,3,White] setSquare[1,0,Black] and setSquare[1,1,White] and setSquare[1,2,Black] and setSquare[1,3,White] setSquare[2,0,White] and setSquare[2,1,Black] and setSquare[2,2,White] and setSquare[2,3,White] setSquare[3,0,White] and setSquare[3,1,White] and setSquare[3,2,White] and setSquare[3,3,White] } run example2 for 16 pred noExample () { -- おまけ:マップも自動生成 Answer.width = 4 and Answer.height = 4 } run example2 for 16