数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学用 C++ 找出二进制矩阵中是否存在一个角为 1 的矩形
假设我们有一个二进制矩阵。我们必须找出指定矩阵中是否存在矩形或序列，其四个角均等于 1。该矩阵类似于
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
结果将是 yes。这里存在一个矩形，其角均为 1。
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
为解决这个问题，我们将使用一种有效的方法。我们将遵循以下步骤 −
逐行从上到下扫描矩阵
对于每一行，记住两个 1 的任意组合，并将其推入哈希集中。
如果我们在后面的行中再次找到该组合，则会得到我们的矩形。
示例
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<vector>
using namespace std;
bool isRectanglePresent(const vector<vector<int> >& matrix) {
int rows = matrix.size();
if (rows == 0)
return false;
int columns = matrix[0].size();
unordered_map<int, unordered_set<int> > table;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < columns - 1; ++j) {
for (int k = j + 1; k < columns; ++k) {
if (matrix[i][j] == 1 && matrix[i][k] == 1) {
if (table.find(j) != table.end() && table[j].find(k) != table[j].end())
return true;
if (table.find(k) != table.end() && table[k].find(j) != table[k].end())
return true;
table[j].insert(k);
table[k].insert(j);
}
}
}
}
return false;
}
int main() {
vector<vector<int> > matrix = {
{ 1, 0, 0, 1, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 0, 1, 0 },
{ 1, 0, 1, 0, 1 }
};
if (isRectanglePresent(matrix))
cout << "Rectangle is present";
else
cout << "Rectangle is not present";
}输出
Rectangle is present
更新于：03-1 月-2020
164 次浏览
广告