私はこれを理解するのに苦労しています。宿題ではないことを約束します。
次のような任意のサイズの行列があるとします ((0, 0) は左上隅にあります)。
1 0 0 1 0 0
0 0 1 1 1 0
0 1 1 1 0 0
0 1 1 1 0 0
0 1 0 1 0 0
私は、隣接するすべてのサブマトリックスの座標をそれらのサブマトリックスで見つける方法を見つけようとしています。この例では、次のようなリストを取得する必要があります。
[(2, 1), (3, 3)
(1, 2), (3, 3)]
このようなリストを作成する方法を理解するのに苦労しています。アルゴリズムが効率的ではないことはわかっています (O(n^2) と推測しています)。これは問題ありません。これは、使用する行列がそれほど大きくないためです。
これを理解する手がかりを私に与えるだけでも大歓迎です。
あなたが持つことができる最善の解決策は、これがあなたが持つことができる答えの最大サイズであるため、O(N^4) です (すべての値が 1 の場合)。
O(N^4) ソリューションを作成するには、次のようにします。サイズ O(N^2) のヘルパー配列を使用し、そのセルのそれぞれに、左上隅が (0,0) の部分行列に 1 の数を格納します。 ) および指定されたセルの右下隅。この配列を使用すると、行列内の 1 の数を計算できます(a,b)(左上) -> (c,d)(右下) 常に次を使用します。
num_of_ones(a,b,c,d) = helper_matrix[c][d] + helper_matrix[a-1][b-1] -helper_matrix[a-1][d] -helper_matrix[c][b-1].
a-1またはb-1が配列から外れる場合に注意してください。
上記のチェックを使用して、各部分行列が 1 だけで満たされている (つまり、その中の 1 の数が部分行列のサイズに等しい) かどうかを確認します。