資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式，用於找出清潔機器人在一個網格中可以清潔的最大細胞數
假設我們正在製作一個在網格上工作的清潔機器人。網格的尺寸為h x w。有m個需要清潔的髒細胞，這些細胞以整數對陣列'dirt'的形式給出。如果將清潔機器人放置在特定單元格中；它可以清潔該特定行和列中的每個單元格。因此，我們的任務是清潔最大數量的髒細胞。我們必須找出數量並將其顯示為輸出。
因此，如果輸入類似於h = 3，w = 3，m = 3，dirt = {{0, 0}, {1, 1}, {2, 1}}，則輸出將為3。如果我們將清潔機器人放置在單元格{1, 0}處，則它將能夠清潔網格中的所有髒細胞。
為了解決這個問題，我們將遵循以下步驟：
Define one map Define two arrays hcount and wcount of size: 100 and initialize with 0 maxh = 0, maxw = 0, res = 0 Define two arrays p, q for initialize i := 0, when i < m, update (increase i by 1), do: a := first value of dirt[i] b := second value of dirt[i] pairMap[pair (a, b)] := 1 (increase hcount[a] by 1) (increase wcount[b] by 1) for initialize i := 0, when i < h, update (increase i by 1), do: maxh := maximum of maxh and hcount[i] for initialize i := 0, when i < w, update (increase i by 1), do: maxw := maximum of maxw and wcount[i] for initialize i := 0, when i < h, update (increase i by 1), do: if hcount[i] is same as maxh, then: insert i at the end of p for initialize i := 0, when i < w, update (increase i by 1), do: if wcount[i] is same as maxw, then: insert i at the end of q for each element i in p, do: for each element j in q, do: if pairMap[pair (i, j)] is non-zero, then: res := maxh + maxw - 1 Otherwise, res := maxh + maxw return res return res
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int solve(int h, int w, int m, vector<pair<int, int>> dirt){
map<pair<int, int>, int> pairMap;
int hcount[100] = {0}, wcount[100] = {0}, maxh = 0, maxw = 0, res = 0;
vector<int>p, q;
for (int i = 0; i < m; i++) {
int a = dirt[i].first;
int b = dirt[i].second;
pairMap[make_pair(a, b)] = 1;
hcount[a]++;
wcount[b]++;
}
for (int i = 0; i < h; i++)
maxh = max(maxh, hcount[i]);
for (int i = 0; i < w; i++)
maxw = max(maxw, wcount[i]);
for (int i = 0; i < h; i++){
if (hcount[i] == maxh)
p.push_back(i);
}
for (int i = 0; i < w; i++) {
if (wcount[i] == maxw)
q.push_back(i);
}
for (auto i : p) {
for (auto j : q) {
if (pairMap[make_pair(i, j)])
res = maxh + maxw - 1;
else {
res = maxh + maxw;
return res;
}
}
}
return res;
}
int main() {
int h = 3, w = 3, m = 3;
vector<pair<int, int>> dirt = {{0, 0}, {1, 1}, {2, 1}};
cout<< solve(h, w, m, dirt);
return 0;
}輸入
3, 3, 3, {{0, 0}, {1, 1}, {2, 1}}輸出
3
更新於： 2022年2月23日
616 次瀏覽
廣告