สมมติว่าเรามีตัวเลขสองตัว 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
