ধরুন আমাদের দুটি সংখ্যা 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