数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学在 C++ 中计数在二进制矩阵中被 1 阻挡的所有 0
在本教程中，我们将讨论一个程序，该程序用于寻找在二进制矩阵中被 1 阻挡的所有 0 的数量。
为此，我们将提供一个二进制矩阵。我们的任务是查找并计数矩阵中所有被 1 阻挡的 0。
示例
#include <iostream>
using namespace std;
#define Row 4
#define Col 5
int r[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };
bool isSafe(int x, int y, int M[][Col]) {
if (x >= 0 && x <= Row && y >= 0 &&
y <= Col && M[x][y] == 0)
return true;
return false;
}
//performing DFS in the matrix
void DFS(int x, int y, int M[][Col]) {
//marking the node as visited
M[x][y] = 1;
for (int k = 0; k < 4; k++)
if (isSafe(x + r[k], y + c[k], M))
DFS(x + r[k], y + c[k], M);
}
//returning count of blocked 0s
int CountAllZero(int M[][Col]){
for (int i = 0; i < Col; i++)
if (M[0][i] == 0)
DFS(0, i, M);
for (int i = 0; i < Col; i++)
if (M[Row - 1][i] == 0)
DFS(Row - 1, i, M);
for (int i = 0; i < Row; i++)
if (M[i][0] == 0)
DFS(i, 0, M);
for (int i = 0; i < Row; i++)
if (M[i][Col - 1] == 0)
DFS(i, Col - 1, M);
//counting all zeros which are surrounded by 1
int result = 0;
for (int i = 0; i < Row; i++)
for (int j = 0; j < Col; j++)
if (M[i][j] == 0)
result++;
return result;
}
int main(){
int M[][Col] = { { 1, 1, 1, 0, 1 },{ 1, 0, 0, 1, 0 },{ 1, 0, 1, 0, 1 },{ 0, 1, 1, 1, 1 } };
cout << CountAllZero(M) << endl;
return 0;
}输出
4
更新于:2020 年 2 月 5 日
220 次浏览
广告