r行c列のすべてのセルを黒にするために必要な最小数の操作を見つけるC++プログラム

2つの数値r、cとサイズnxmのグリッドがあるとします。一部のセルは黒で、残りは白です。 1つの操作で、いくつかの黒いセルを選択し、これら2つのうちの1つを正確に実行できます-

• 行のすべてのセルを黒に着色するか、
• 列のすべてのセルを黒に着色します。

行rと列cのセルを黒にするために必要な操作の最小数を見つける必要があります。不可能な場合は、-1を返します。

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

r=0およびc=3

この場合、出力は1になります。これは、最初の行を変更して、これを-

ステップ

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

n := row count of grid
m := column count of grid
ans := inf
for initialize i := 0, when i < n, update (increase i by 1), do:
   for initialize j := 0, when j < m, update (increase j by 1), do:
      if matrix[i, j] is same as 'B', then:
         ans := minimum of ans and (1 if i and r are different, otherwise 0) + (1 if j and                c are different, otherwise 0)
if ans > 2, then:
   return -1
Otherwise
   return ans

例

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<vector<char>> matrix, int r, int c) {
   int n = matrix.size();
   int m = matrix[0].size();
   int ans = 999999;
   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
         if (matrix[i][j] == 'B') {
            ans = min(ans, (i != r) + (j != c));
         }
      }
   }
   if (ans > 2) {
      return -1;
   }
   else
      return ans;
}
int main() {
   vector<vector<char>> matrix = { { 'W', 'B', 'W', 'W', 'W' }, { 'B', 'B', 'B', 'W', 'B'          }, { 'W', 'W', 'B', 'B',          'B' } };
   int r = 0, c = 3;
   cout << solve(matrix, r, c) << endl;
}

入力

{ { 'W', 'B', 'W', 'W', 'W' }, { 'B', 'B', 'B', 'W', 'B' }, { 'W', 'W', 'B', 'B', 'B' } }, 0, 3

出力

1