Spaceship landing strip (Scientific Expedition) - 最大の着陸場を探せ

どんな問題？

Spaceship landing strip
http://www.checkio.org/mission/spaceship-landing-strip/

地形データから、最大の着陸場を探せ。
地形には、草地、岩、水、低木、高木の5種類あり、草地と低木は整地可能である。
整地可能な地形のみでできた最大の長方形を探し、その面積を求めよ。

地形コード

G	grass	草地	○
R	rock	岩	×
W	water	水	×
S	shrubs	低木	○
T	trees	高木	×

ようするに、地形データから、GとSのみで作られる最大の長方形を探す問題。

引数は、文字列のリストで地形データが渡される。
戻り値は、最大の着陸場の面積を返す。
マップの大きさは縦横10未満。

例題：

checkio(['G']) == 1
checkio(['GS','GS']) == 4
checkio(['GT','GG']) == 2
checkio(['GGTGG','TGGGG','GSSGT','GGGGT','GWGGG','RGTRT','RTGWT','WTWGR']) == 9

どうやって解く？

整地可能なマス（GとS）のみで作られる最大の長方形をどうやって探せばいいだろうか？
マップサイズもそれほど大きくないので、総当たりでチェックするとしよう。

長方形は、左上の点（始点）と右下の点（終点）で定義できるので、

• すべてのマスから１つのマスを選んで始点とする
• 始点の右下方向にあるマスから１つ選んで終点とする
• 長方形が整地可能なら、その面積を取得する
• すべての長方形を調べて、最大の面積を求める

という流れかな。

まず、長方形の中のすべてのマス（座標）を列挙する関数を作成した。

def enum_pts_in_rect(left_top, right_bottom):
    for y in range(left_top[1], right_bottom[1] + 1):
        for x in range(left_top[0], right_bottom[0] + 1):
            yield x, y

指定のマスが整地可能かどうかは、

    def can_land(pt):
        return landing_map[pt[1]][pt[0]] in 'SG'

でチェックする。
始点(src)から、最大の長方形の面積を取得する関数はこちら。

    def get_max_area(src):
        result = 0
        # 始点からマップ右下までのマスが、終点の候補
        for dest in enum_pts_in_rect(src, map_right_bottom):
            # 長方形の中のマスをリストアップ
            pts = list(enum_pts_in_rect(src, dest))
            if all(can_land(pt) for pt in pts):  # すべてのマスが整地可能なら
                result = max(result, len(pts))  # マスの数＝面積
        return result

まとめたのがこちら

def enum_pts_in_rect(left_top, right_bottom):
    # Yields (x,y) in rect
    for y in range(left_top[1], right_bottom[1] + 1):
        for x in range(left_top[0], right_bottom[0] + 1):
            yield x, y

def checkio(landing_map):
    def can_land(pt):
        return landing_map[pt[1]][pt[0]] in 'SG'

    def get_max_area(src):
        result = 0
        for dest in enum_pts_in_rect(src, map_right_bottom):
            pts = list(enum_pts_in_rect(src, dest))
            if all(can_land(pt) for pt in pts):
                result = max(result, len(pts))
        return result

    map_right_bottom = len(landing_map[0]) - 1, len(landing_map) - 1
    return max(get_max_area(pt) for pt in enum_pts_in_rect((0, 0), map_right_bottom))

http://www.checkio.org/mission/spaceship-landing-strip/publications/natsuki/python-3/first/

クリア＆公開！

ちょっと書き直してみた。

見直すと、なんか読みにくい気がするので、ちょっと修正。

def checkio(landing_map):
    def pts_in_rect(start, end):
        # Yields (x,y) in rect
        for y in range(start[1], end[1] + 1):
            for x in range(start[0], end[0] + 1):
                yield x, y
    
    def can_land(rect):
        return all(landing_map[pt[1]][pt[0]] in 'SG' for pt in pts_in_rect(*rect))

    def get_area(rect):
        return len(list(pts_in_rect(*rect)))

    map_end = len(landing_map[0]) - 1, len(landing_map) - 1
    rects = [(start, end) for start in pts_in_rect((0, 0), map_end) for end in pts_in_rect(start, map_end)]
    return max(get_area(rect) for rect in rects if can_land(rect))

うーん、改めて公開するほどでもないか。

他の人の答え

最初よくわからなかったのがこちら。

def checkio(a):
    """
    A plain O(N^2*M^2) algorithm, where c[i][j] is the number of obstacles
    in the rectangle from the top-left corner to (and including) (i, j).
    """
    n, m = len(a), len(a[0])
    c = defaultdict(int)
    for i in range(n):
        for j in range(m):
            c[i,j] = c[i-1,j] + c[i,j-1] - c[i-1,j-1]
            if a[i][j] in "WRT":
                c[i,j] += 1
    best = 0
    for i1 in range(-1, n):
        for j1 in range(-1, m):
            for i2 in range(i1+1, n):
                for j2 in range(j1+1, m):
                    if c[i2,j2] - c[i1,j2] - c[i2,j1] + c[i1,j1] == 0:
                        best = max(best, (i2-i1)*(j2-j1))
    return best

http://www.checkio.org/mission/spaceship-landing-strip/publications/nickie/python-3/simple-on2m2/

最初に、c[i,j]というdictを作成している。コメントにあるように、c[i,j]は、マップ左上から自分(i,j)までの長方形内の障害物の数となる。

このdictを作成するのが、この部分。

c[i,j] = c[i-1,j] + c[i,j-1] - c[i-1,j-1]
if a[i][j] in "WRT":
    c[i,j] += 1

[i-1,j]は一つ上のマス、[i,j-1]は左隣のマス、[i-1,j-1]は左上のマスとなる。
下の図でいえば、c[i-1,j]は赤いエリアの障害物の数、c[i,j-1]は青いエリアの障害物の数、c[i-1,j-1]は緑のエリアの障害物の数となる。
だから、赤＋青－緑　そして、[i,j]が障害物なら+1することで、c[i,j]が求められるというわけだ。

こうして、各マスごとに障害物の数を調べておけば、左上(i1,j1)、右下(i2,j2)の長方形の障害物の数は、

c[i2,j2] - c[i1,j2] - c[i2,j1] + c[i1,j1]

で求められる。

この方法だと、障害物のチェック回数が減るので効率的ということらしい。
なんだか、昨日の The pseudo-polynomial algorithm にも、似ている気がする。

いやー、こんなの自分では絶対に思い付けない。勉強になった。