オフラインリアルタイムどう書く E32 の実装例( python ) #Python

問題の名前 : きれいな四角
問題 : http://nabetani.sakura.ne.jp/hena/orde32rects/
実装リンク集 : https://qiita.com/Nabetani/items/bd16f3fa1d9e4d0d60ae

で。

会場で提示だけしたアイディアを Python3 で実装した。

こんな感じ。

Python3

import cv2
import sys
import json
import numpy as np
from copy import deepcopy

WH=36

def newRect(s):
  s36 = "0123456789abcdefghijklmnopqrstuvwxyz"
  x, y, r, b = [s36.index(x) for x in s ]
  return (x+1, y+1, r+1, b+1)

def findRect(field0, x, y):
  field = deepcopy(field0)
  h, w = field.shape[:2]
  mask0 = np.zeros((h + 2, w + 2, 1), dtype=np.uint8)
  _, _, mask, box = cv2.floodFill(
      field, mask0, seedPoint=(x, y), newVal=1)
  filled = mask[1:(h+1),1:(w+1)]
  if box[2] * box[3] == cv2.countNonZero(filled):
    return box, filled
  return None, filled

def buildField(src):
  field = np.zeros((WH+1, WH+1, 3), np.uint8)
  col=1
  for r in [ newRect(s) for s in src.split("/") ]:
    field[r[0]:r[2], r[1]:r[3]]+=np.array([col&255,col//256,0], np.uint8)
    col <<= 1
  return field

def collectSizes(field):
  checked = np.zeros((WH+1, WH+1, 1), np.uint8)
  sizes=[]
  for y in range(1,WH):
    for x in range(1,WH):
      if 0 != checked[y,x][0]:
        continue
      r, ch = findRect( field, x, y )
      checked += ch
      if r:
        sizes.append(r[2]*r[3])
  return sizes

def solve(src):
  field = buildField(src)
  sizes = collectSizes(field)
  return ",".join([str(s) for s in sorted(sizes)])

with open(sys.argv[1], "r") as file:
  data = json.load(file)
  for case in data["test_data"]:
    actual = solve( case["src"] )
    ok = actual == case["expected"]
    print( ("ok" if ok else "**NG**"), case["src"], actual, case["expected"] )

入力は JSON で、コマンドライン引数で与える。

戦略としては。

地図を作る
地図を塗る
塗った範囲が四角ければ、それはきれいな四角なので、サイズを計算してリストに追加する
出来上がったリストを整形して返せば OK

というもの。

地図はセルの集まりになっている。
セルの色は、そのセルを含んでいる矩形のリストを意味している。
具体的には、n番目の矩形の内側ならn番目のビットが立っている2進数……にしたかったんだけど、OpenCV の制約で 8bit-color にしなければならず、そこはちょっとごちゃごちゃしている。

地図ができたら、cv2::floodFill で地図を塗る。
都合のいいことに cv2::floodFill は

塗った範囲の外接矩形
塗った範囲を 1 とする白黒画像

を返してくれる。
前者の面積と後者の非ゼロの点の数が一致していれば四角く塗ったことになるので、それがきれいな四角である。

一度塗られたことがある領域は調べなくて良いので、それを checked に覚えてもらって適宜スキップする。

OpenCV がなくても、floodFill さえ実装すれば同じ戦略で解くことができる。

今回は OpenCV を使っている関係で、画素値に 24bit しか使えない。矩形の数が 24 を超えたらなんか考える必要があるけど、今回は 9個が最大なのでこれで大丈夫。