Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

r 행 c 열의 모든 셀을 검정색으로 만드는 데 필요한 최소 작업 수를 찾는 C++ 프로그램

<시간/>

두 개의 숫자 r, c와 크기가 n x m인 격자가 있다고 가정합니다. 일부 셀은 검은색이고 나머지 셀은 흰색입니다. 한 번의 작업으로 일부 검은색 셀을 선택할 수 있으며 이 두 가지 중 정확히 하나를 수행할 수 있습니다. -

  • 행의 모든 ​​셀을 검정색으로 지정하거나
  • 열의 모든 셀을 검정색으로 지정합니다.

r행과 c열의 셀을 검정색으로 만드는 데 필요한 최소 연산 수를 찾아야 합니다. 불가능하면 -1을 반환합니다.

따라서 입력이 다음과 같으면

W B W W W
B B B W B
W W B B B

r =0 및 c =3

첫 번째 행을 다음과 같이 변경할 수 있기 때문에 출력은 1이 됩니다. -

B B B B B
B B B W B
W W B B B

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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