मान लीजिए कि हमारे पास दो संख्याएँ r, c और n x m आकार की एक ग्रिड है। कुछ कोशिकाएँ काले रंग में और शेष सफेद रंग की होती हैं। एक ऑपरेशन में, हम कुछ काली कोशिकाओं का चयन कर सकते हैं और इन दोनों में से ठीक एक कर सकते हैं -
- इसकी पंक्ति के सभी कक्षों को काला रंग दें, या
- इसके कॉलम के सभी सेल को काला रंग दें।
हमें पंक्ति r और स्तंभ c में सेलों को काला बनाने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी है। यदि असंभव हो, तो -1 लौटें।
तो, अगर इनपुट पसंद है
| W | B | W | W | W |
| B | B | B | W | B |
| W | W | B | B | B |
आर =0 और सी =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