C++ 中的布尔矩阵问题?
c++server side programmingprogramming
这里我们将看到一个有趣的布尔矩阵问题。给定一个包含 0 和 1 的布尔矩阵。我们的目标是找到 1 被标记的位置。如果 1 被标记为 mat[i,j] 的位置，那么我们将使行 i 和列 j 的所有条目都进入 1。让我们看一个例子。如果矩阵如下 −
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
那么修改后就是 −
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1
算法
matrixUpdate(matrix[R,C])
begin 定义两个矩阵row[R]和col[C]，并用0填充 标记 mat[R,C] 的行和列索引，其中 1 被放入 row[R] 和 col[C] 矩阵中 检查 row[R] 和 col[C] 是否标记了该位置，然后用 1 填充该行和列的所有位置。 end
示例
#include <iostream>
#define R 4
#define C 4
using namespace std;
void updateMatrix(bool mat[R][C]) {
bool row[R];
bool col[C];
int i, j;
for (int i = 0; i < R; i++) { //将行矩阵的所有元素设置为 0
row[i] = 0;}
for (i = 0; i < C; i++) { //将列矩阵的所有元素设置为 0
col[i] = 0;}
for (int i = 0; i < R; i++) { //标记行和列矩阵以确定 1 存在的位置
for (int j = 0; j < C; j++) {
if (mat[i][j] == 1) {
row[i] = 1;
col[j] = 1;
}
}
}
for (i = 0; i < R; i++) { //将行和列全部设置为 1，其中 1 被标记
for (j = 0; j < C; j++) {
if ( row[i] == 1 || col[j] == 1 ) {
mat[i][j] = 1;
}
}
}
}
void displayMatrix(bool mat[R][C]) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cout << mat[i][j];
}
cout << endl;
}
}
main() {
bool mat[R][C] = { {1, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 0, 0}
};
cout << "给定矩阵" << endl;
displayMatrix(mat);
updateMatrix(mat);
cout << "更新矩阵" << endl;
displayMatrix(mat);
}
输出
给定矩阵 1001 0000 0000 0100 更新矩阵 1111 1101 1101 1111
