/*
Given a matrix of size n x m filled with 0's and 1's
e.g.:
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
if the matrix has 1 at (i,j), fill the column j and row i with 1's
i.e., we get:
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
complexity: O(n*m) time and O(1) space
NOTE: you are not allowed to store anything except
'0' or '1' in the matrix entries
*/
#include <stdio.h>
static const int ROWS = 4;
static const int COLS = 5;
void print_array(int arr[][COLS], const int& rows, const int& cols)
{
for (int j = 0; j < rows; ++j) {
for (int i = 0; i < cols; ++i)
printf("%d ", arr[j][i]);
printf("\n");
}
printf("\n");
}
void set_ones(int arr[][COLS], const int& rows, const int& cols)
{
int curval;
/* Update the table headers */
for (int j = 1; j < rows; ++j){
for (int i = 1; i < cols; ++i){
curval = arr[j][i];
if (1 == curval){
/* Update the row info */
arr[j][0] = curval;
/* Update the column info */
arr[0][i] = curval;
}
}
}
printf("After headers update\n");
print_array(arr, rows, cols);
/* Update the inner matrix */
for (int j = 1; j < rows; ++j){
for (int i = 1; i < cols; ++i){
if (arr[j][0] == 1 || arr[0][i] == 1)
arr[j][i] = 1;
}
}
printf("After inner matrix update\n");
print_array(arr, rows, cols);
if (arr[0][0] == 1){
/* Update the inner matrix */
for (int j = 0; j < rows; ++j){
for (int i = 0; i < cols; ++i){
if (j == 0 || i == 0)
arr[j][i] = 1;
}
}
}
printf("After processing the matrix header\n");
print_array(arr, rows, cols);
}
int main()
{
int arr[ROWS][COLS] = {
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0,},
{0, 1, 0, 0, 0,},
{1, 0, 1, 1, 0,}
};
printf("Original matrix:\n");
print_array(arr, ROWS, COLS);
set_ones(arr, ROWS, COLS);
return 0;
}