Pythonで指定された3つの頂点から長方形の4番目の頂点の座標を求める方法

Q × P のサイズのグリッドを考えてみましょう。このグリッドには、ちょうど3つのアスタリスク「*」が含まれており、その他のセルはすべてドット「.」で埋められています。「*」は長方形の頂点を表しています。ここでの課題は、欠けている4番目の頂点の座標を見つけることです。なお、座標は1始まりのインデックス(1-based indexing)として扱います。

たとえば、入力が grid = ["*..", "...", "*.*"] の場合、出力は (1, 3) になります。これが求める、欠けている頂点の座標です。

アプローチ：行と列の出現回数を数える

この問題は、各行・各列に含まれる「*」の個数に着目することで効率的に解けます。グリッドに沿って配置された長方形の頂点は、必ず2つの行と2つの列にまたがって存在します。3つの頂点がすでに分かっている状態では、「*」が1個だけ含まれる行と列がそれぞれ1つずつ存在し、その交点こそが欠けている4番目の頂点に該当します。

具体的には、次の手順で解きます。

1. p := グリッドの行数、q := グリッドの列数とします。
2. 行番号をキー、出現回数を値とするマップ row を作成し、すべての値を 0 で初期化します。
3. 同様に、列番号をキーとするマップ col を作成します。
4. i を 0 から p−1 まで、j を 0 から q−1 までの二重ループでグリッドを走査し、grid[i][j] が「*」であれば row[i] と col[j] をそれぞれ +1 します。
5. row の中で値が 1 になっている行番号を x_coord とします。
6. col の中で値が 1 になっている列番号を y_coord とします。
7. (x_coord + 1, y_coord + 1) を返します(+1 は1始まりのインデックスへの変換です)。

Pythonによる実装例

理解を深めるために、実際の実装を見てみましょう。

def get_missing_vertex(grid) :
    p = len(grid)
    q = len(grid[0])
    row = dict.fromkeys(range(p), 0)
    col = dict.fromkeys(range(q), 0)
    for i in range(p) :
        for j in range(q) :
            if (grid[i][j] == '*') :
                row[i] += 1
                col[j] += 1
    for k,v in row.items() :
        if (v == 1) :
            x_coord = k
    for k,v in col.items() :
        if (v == 1) :
            y_coord = k
    return (x_coord + 1, y_coord + 1)
grid = ["*..", "...", "*.*"]
print(get_missing_vertex(grid))

入力

["*..", "...", "*.*"]

出力

(1, 3)

動作の解説

この入力の場合、アスタリスクは0始まりの座標で (0, 0)、(2, 0)、(2, 2) の位置にあります。行ごとに数えると、行0に1個、行2に2個の「*」があるため、x_coord は 0 となります。同様に列ごとに数えると、列2だけが1個であるため、y_coord は 2 となります。最後に1始まりの座標へ変換し、(1, 3) が出力される仕組みです。

計算量： グリッド全体を一度だけ走査するため、時間計算量は O(p × q)。行・列ごとのカウント用マップが必要になるため、空間計算量は O(p + q) となります。非常にシンプルながら、グリッドサイズが大きくなっても安定した性能を発揮できる手法です。