カウントNo。マトリックスから与えられた制約を持つ部分行列の？

Question

これは1つの就職面談で尋ねられる質問です。希望の結果を得るための最適な最適アルゴリズムを知りたい。 質問は次のとおりです。あなたには、（n×m）の行列があり、そこにいくつかの数が入っているとします。 は今、あなたはサイズの行列の何をカウントする必要はない>の二つの条件以下きます=（2×2）：それは持つべき

• をAT-少なくとも二つの1の。
• 行列の2つの角要素が等しい。

私は行列2 x 2以上のすべての要素を取るブルートフォースアルゴリズムを知っています。その後、それらのうちの2つが等しい等しい6つのコーナー要素の可能な条件を調べることによって、 「GeeksForGeeks」またはStackOverFlowで、これらの問題またはソースを処理する方法を最も最適化された方法で知りたいと思います。

Answer 1

これは、最適化された方法のヒントです。

まず部分行列（1-I、1-J）で1の数をカウント（N、M）行列を構築：N メートル操作、n個の各要素の

今メートルメモリ同じ列に、使用できるかどうか2つのコーナーが

に等しいとあなたはマトリックスを有するように以下の任意の行を使用することができ、同じ行の場合

• 等しい以下の後のすべての要素のためのマトリックス、検索2つのコーナーが
• 同じ行でも同じ列でもない場合、2つのコーナーを持つ1つの行列があります。
• 事前計算された等価行列の極端な要素の差は、サブマトリックスの1の数です
• とすぐに1つの部分行列はそれに2つの以上のものを持っているとして、それを含むすべての部分行列もあります：あなたは上記のが唯一の荒削りであり、いくつかがまだある

短絡完全な分析にそれを使用することができますalgorythmを設計する作業をしますが、それは十分大きな行列のためのブルートフォースよりも少し良いはずです...