資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式，用於查詢使r行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
更新於: 2022年3月3日
197 次檢視
廣告