C++で黒いピクセルを囲む最小の長方形

画像があり、その画像が、0が白のピクセル、1が黒のピクセルのバイナリ行列で表されているとします。ここでは黒いピクセルが接続されているため、黒い領域は1つだけです。ピクセルは水平方向と垂直方向に接続されています。黒のピクセルの1つの位置（x、y）がある場合、すべての黒のピクセルを囲む最小の（軸に沿った）長方形の領域を見つける必要があります。

したがって、入力が次のような場合

x =0、y =2の場合、出力は6になります

これを解決するには、次の手順に従います-

• 1つの2Dアレイvを定義する

• 関数searchRows（）を定義します。これには、i、j、左、右、1つが必要です

• i

  • mid：=i +（j --i）/ 2

  • k：=左

  • （k<右およびv[mid、k]は '0'と同じ）、do-

    • （kを1増やします）

  • k <'rightが1と同じ場合、-

    • j：=mid

  • それ以外の場合

    • i：=mid + 1

• iを返す

• 関数searchColumn（）を定義します。これには、i、j、top、bottom、one、

  が必要です。

• iがjと等しくない場合は、次のようにします-

  • mid：=i +（j --i）/ 2

  • k：=トップ

  • （k

    • （kを1増やします）

  • k

    • j：=mid

  • それ以外の場合

    • i：=mid + 1

• iを返す

• メインの方法から、次のようにします-

• v：=画像

• ret：=0

• n：=画像の行サイズ

• m：=画像の列サイズ

• top：=searchRows（0、x、0、m、true）

• 下：=searchRows（x + 1、n、0、m、false）

• 左：=searchColumn（0、y、top、bottom、true）

• 右：=searchColumn（y + 1、m、top、bottom、false）

• 戻る（右-左）*（下-上）

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < vector <char> > v;
   int searchRows(int i, int j, int left, int right, bool one){
      while (i < j) {
         int mid = i + (j - i) / 2;
         int k = left;
         while (k < right && v[mid][k] == '0')
            k++;
         if (k < right == one) {
            j = mid;
         }
         else {
            i = mid + 1;
         }
      }
      return i;
   }
   int searchColumn(int i, int j, int top, int bottom, bool one){
      while (i != j) {
         int mid = i + (j - i) / 2;
         int k = top;
         while (k < bottom && v[k][mid] == '0')
            k++;
         if (k < bottom == one) {
            j = mid;
         }
         else {
            i = mid + 1;
         }
      }
      return i;
   }
   int minArea(vector<vector<char>>& image, int x, int y) {
      v = image;
      int ret = 0;
      int n = image.size();
      int m = image[0].size();
      int top = searchRows(0, x, 0, m, true);
      int bottom = searchRows(x + 1, n, 0, m, false);
      int left = searchColumn(0, y, top, bottom, true);
      int right = searchColumn(y + 1, m, top, bottom, false);
      return (right - left) * (bottom - top);
   }
};
main(){
   Solution ob;
   vector<vector<char>> v =
   {{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}};
   cout << (ob.minArea(v, 0, 2));
}

入力

{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}, 0, 2

出力

6