In this question, we have to travel the matrix twice. In the first time, we need to record which rows and columns contain zero element. And in the second round, we will set these rows and columns entirely zero.
By the way, in this case, we could not set zero while in the first travel. If we did so, once meet with a zero element, we set its entire row and column to zero. It might change some of the remaining non-zero element to zero. Later, when we meet with these changed elements, we will set its entire row and column to zero, while we should not.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-03-23 10:38 # Filename: 1.7.c # Description: in a matrix, any entire row or column will be set to zero, if it contains one or more zero element. =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <limits.h> void print_matrix(int **matrix, int size_r, int size_c){ // Print out the matrix as size_r*size_c int index_r = 0, index_c = 0; if(size_r<=0 || size_c<=0){ printf("Invalid argument for matrix size.n"); return; } for(index_r = 0; index_r < size_r; ++index_r){ printf("%d",matrix[index_r][0]); for(index_c = 1; index_c < size_c; ++index_c){ printf("t%d",matrix[index_r][index_c]); } printf("n"); } return; } int set_zero(int **matrix, int size_r, int size_c){ // Set any entire row or column to zeor, if it contains // an element being zeor. // Return value: 0 for success, and -1 for failure char *row = NULL, *column = NULL; int index_r = 0, index_c = 0; // Allocate memory for bitmap of rows row = (char *) malloc(size_r%CHAR_BIT==0 ? sizeof(char)* (size_r/CHAR_BIT) : sizeof(char)* (size_r/CHAR_BIT + 1)); if(row == NULL){ return -1; } memset(row, 0, (size_r%CHAR_BIT==0 ? sizeof(char)* (size_r/CHAR_BIT) : sizeof(char)* (size_r/CHAR_BIT + 1))); // Allocate memory for bitmap of columns column = (char *) malloc(size_c%CHAR_BIT==0 ? sizeof(char)* (size_c/CHAR_BIT) : sizeof(char)* (size_c/CHAR_BIT + 1)); if(column == NULL){ free(row); return -1; } memset(column, 0, (size_c%CHAR_BIT==0 ? sizeof(char)* (size_c/CHAR_BIT) : sizeof(char)* (size_c/CHAR_BIT + 1))); // Set the bitmaps of rows and columns for(index_r = 0; index_r < size_r; ++index_r){ for(index_c = 0; index_c < size_c; ++index_c){ if(matrix[index_r][index_c] == 0){ row[index_r/CHAR_BIT] |= (1 << (index_r % CHAR_BIT)); column[index_c/CHAR_BIT] |= (1 << (index_c % CHAR_BIT)); } } } // Set all rows, that contain zero element, to zero entirely for(index_r = 0; index_r < size_r; ++index_r){ if((row[index_r/CHAR_BIT] & (1 << (index_r % CHAR_BIT))) != 0){ for(index_c = 0; index_c < size_c; ++index_c){ matrix[index_r][index_c] = 0; } } } // Set all columns, that contain zero element, to zero entirely for(index_c = 0; index_c < size_c; ++index_c){ if((column[index_c/CHAR_BIT] & (1 << (index_c % CHAR_BIT))) != 0){ for(index_r = 0; index_r < size_r; ++index_r){ matrix[index_r][index_c] = 0; } } } free(row); free(column); return 0; } void free_matrix(int32_t **matrix, int size){ // Free the allocated memory for matrix int index = 0; if(matrix == NULL){ return; } for(index=0; index<size; ++index){ if(matrix[index] != NULL){ free(matrix[index]); } } free(matrix); return; } int main(int argc, char **argv){ // The matrix must be a square matrix int **matrix = NULL; int size_r = 0, size_c = 0, index_outer = 0, index_inner=0; int result; // Check and get argument if(argc != 3){ printf("Invalid arguments.n"); printf("Usage: %s matrix_height matrix_widthn",argv[0]); return 1; } size_r = atoi(argv[1]); size_c = atoi(argv[2]); if(size_r < 1 || size_c < 1){ printf("Invalid matrix size: %s by %s.n", argv[1], argv[2]); printf("Usage: %s matrix_height matrix_widthn",argv[0]); return 2; } // Prepare the test matrix matrix = (int **) malloc(sizeof(int *)*size_r); if(matrix == NULL){ printf("Fail to allocate memory.n"); return 3; } memset(matrix, 0, sizeof(int *)*size_r); srand(time(NULL)); for(index_outer = 0; index_outer < size_r; ++index_outer){ matrix[index_outer] = (int *) malloc(sizeof(int)*size_c); if(matrix[index_outer] == NULL){ printf("Fail to allocate memory.n"); free_matrix(matrix, size_r); return 3; } for(index_inner=0; index_inner < size_c; ++index_inner){ // Set the probability of any element being zero as 10% if(rand()%10 == 0){ matrix[index_outer][index_inner] = 0; } else{ matrix[index_outer][index_inner]= index_outer * size_c + index_inner + 1; } } } // Call function to rotate it printf("Before setting zero:n"); print_matrix(matrix, size_r, size_c); result = set_zero(matrix,size_r, size_c); if(result == 0){ printf("After setting zero:n"); print_matrix(matrix,size_r, size_c); } else{ printf("Error in setting zero.n"); } free_matrix(matrix, size_r); return 0; } |