資料結構
網路
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 次瀏覽
廣告