Pythonで解く「グリッドイルミネーション」問題 ― 行・列・斜めの照光判定を効率化する方法

問題の概要

N×N のマス目からなるグリッドがあり、各マス (x, y) にはランプが1つずつ設置されています。初期状態では一部のランプのみが点灯しており、点灯している i 番目のランプの位置は lamps[i] で与えられます。

点灯しているランプは、それぞれ同じ行(x軸方向)、同じ列(y軸方向)、そして両方の斜め方向にあるすべてのマスを照らします。

i 番目のクエリ queries[i] = (x, y) に対しては、マス (x, y) が照らされていれば 1、そうでなければ 0 を返します。さらに、各クエリの処理後には、そのマス自身および周囲8方向に隣接するマスにあるランプをすべて消灯しなければなりません。

最終的に、各クエリへの回答を順番に格納した配列 answer を返してください。answer[i] は i 番目のクエリ queries[i] の結果と一致する必要があります。

入力例

N = 5、lamps = [[0,0],[4,4]]、queries = [[1,1],[1,0]] の場合、出力は [1, 0] となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• lamps を、与えられた配列から生成した座標ペア(タプル)の集合として保持します

• x、y、diag1、diag2 という4つのカウンタ用辞書(defaultdict)を作成します

• lamps 内の各ペア (i, j) について:

  • x[i] += 1、y[j] += 1 とカウントを増やします

  • diag1[i + j] += 1、diag2[i − j] += 1 とカウントを増やします

• ans := [](空の配列)を用意します

• クエリ C 内の各値 i について:

  • a := i[0]、b := i[1] とします

  • x[a] + y[b] + diag1[a + b] + diag2[a − b] > 0 なら 1、そうでなければ 0 を ans に追加します

  • row を a − 1 から a + 1 まで繰り返し:

    • col を b − 1 から b + 1 まで繰り返し:

      • (row, col) が lamps に存在する場合:

        • x[row] -= 1

        • y[col] -= 1

        • diag1[row + col] -= 1

        • diag2[row − col] -= 1

        • lamps から (row, col) を削除します

• ans を返します

このアルゴリズムのポイント

鍵となるのは、照光判定を O(1) で行える構造にすることです。行・列・斜め線ごとに点灯ランプの数を事前にカウントしておけば、任意のマス (a, b) が照らされているかは次の4つの値を見るだけで判定できます。

• x[a]:行 a 上の点灯ランプ数

• y[b]:列 b 上の点灯ランプ数

• diag1[a + b]:左下〜右上方向の斜め線(i + j が一定)上の点灯ランプ数

• diag2[a − b]:左上〜右下方向の斜め線(i − j が一定)上の点灯ランプ数

また、クエリ処理後に周囲9マス(自身+8方向)のランプを消す際も、該当するカウンタを減算して集合から削除するだけで済みます。これにより、全体的な計算量はクエリ数とランプ数に対してほぼ線形時間に抑えられ、大規模な入力でも高速に動作します。

Pythonでの実装例

from collections import defaultdict
class Solution(object):
    def gridIllumination(self, N, b, C):
        lamps = {(i[0], i[1]) for i in b}
        x, y, diag1, diag2 = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)
        for i, j in lamps:
            x[i] += 1
            y[j] += 1
            diag1[i + j] += 1
            diag2[i - j] += 1
        ans = []
        for i in C:
            a = i[0]
            b = i[1]
            ans.append(1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0)
            for row in range(a - 1, a + 2):
                for col in range(b - 1, b + 2):
                    if (row, col) in lamps:
                        x[row] -= 1
                        y[col] -= 1
                        diag1[row + col] -= 1
                        diag2[row - col] -= 1
                        lamps.remove((row, col))
        return ans

ob = Solution()
N = 5
lamps = [[0,0],[4,4]]
query = [[1,1],[1,0]]
print(ob.gridIllumination(N, lamps, query))

入力

5, [[0,0],[4,4]], [[1,1],[1,0]]

出力

[1, 0]

まとめ

グリッドイルミネーション問題は、素朴に実装すると各クエリごとに全ランプを確認する必要があり非効率ですが、「行・列・斜め線ごとのカウント管理」という工夫によって大幅な高速化が可能です。defaultdict を活用したカウンタ更新と、クエリ後の近傍ランプ消灯処理を組み合わせることで、競技プログラミングや実務のデータ処理でも応用できる効率的なソリューションになります。