মান লিখুন: আমাদের কাছে দুটি সংখ্যা 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, কারণ প্রথম সারিটি কালো করলে r সারি এবং c কলাম উভয়ই কালো হয়ে যাবে।
সমাধানের ধাপসমূহ
n := গ্রিডের সারি সংখ্যা
m := গ্রিডের কলাম সংখ্যা
ans := infinity
for i := 0 থেকে n-1:
for j := 0 থেকে m-1:
যদি grid[i][j] == 'B':
ans := min(ans, (i != r ? 1 : 0) + (j != c ? 1 : 0))
যদি ans > 2: -1 রিটার্ন করুন
অন্যথায়: ans রিটার্ন করুন
C++ বাস্তবায়ন
#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
