数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告