二次元いもす法

いもす法とは、要素の重複を効率よく数えるアルゴリズム。
詳細はこちら

今回は2次元に拡張したいもす法をpythonで実装した。

4 5 2
xoooo
oooox
ooooo
oxxoo

これらを入力とする。4 * 5のグリッド内でxのそれぞれを中心とする一辺5の正方形があると考える。
これらの正方形が重なり合ってグリッド上に存在すると考えた時、最も多くの正方形が重なっている座標では何個の正方形が重なっているか、という問題を考える。

r, c, k = map(int, input().split())
grid = [input() for i in range(r)]
cumsum = [[0] * c for i in range(r)]
for y in range(r):
    for x in range(c):
        if grid[y][x] == 'x':
            cumsum[max(0, y - k)][max(0, x - k)] += 1
            if x + k + 1 < c:
                cumsum[max(0, y - k)][x + k + 1] -= 1
            if y + k + 1 < r:
                cumsum[y + k + 1][max(0, x - k)] -= 1
            if y + k + 1 < r and x + k + 1 < c:
                cumsum[y + k + 1][x + k + 1] += 1



for y in range(r):
    for x in range(c - 1):
        cumsum[y][x + 1] += cumsum[y][x]



for x in range(c):
    for y in range(r - 1):
        cumsum[y + 1][x] += cumsum[y][x]


print(cumsum)

[[1, 1, 2, 1, 1], [3, 3, 4, 3, 2], [3, 3, 4, 3, 2], [2, 2, 3, 3, 2]]

答えは4とわかった。