#include <stdio.h> #include <limits.h> inline void clear(int m, int n, int a[][n], int row, int col) { int k; for(k = 0; k < m; k++) if(a[k][col] != 0) a[k][col] = INT_MAX; for(k = 0; k < n; k++) if(a[row][k] != 0) a[row][k] = INT_MAX; } inline void print(const int m, const int n, int a[][n]) { int i, j; for(i = 0; i < m; i++) { for(j = 0; j < n; j++) printf("%d", a[i][j]); printf("\n"); } } void setRowCol(const int m, const int n, int a[][n]) { int i = 0, j = 0, k; for(i = 0; i < m; i++) for(j = 0; j < n; j++) if(a[i][j] == 0) { clear(m, n, a, i, j); } for(i = 0; i < m; i++) for(j = 0; j < n; j++) if(a[i][j] == INT_MAX) { a[i][j] = 0; } } int main() { int a[][3] = { {2, 0, 4}, {1 ,2, 3}, {3, 5, 0}, {4, 5, 6} }; setRowCol(4, 3, a); print(4, 3, a); }
Advertisements
The code doesn't work for the following input:{2, 0, 4}{1 ,2, 3}{3, 0, 5}{4, 5, 6}What we get is:0 0 01 0 33 0 54 0 6What we should get is:0 0 01 0 30 0 04 0 6We need to separate the logic for detecting zeros from the logic that sets rows & columns to zero .. instead of doing it in-place.
I checked it, that produces correct o/psee http://codepad.org/7S3wUoM4
This code will fail for following array:{2, 0, 4},{INT_MAX ,2, 3},{3, 0, 5},{4, 5, 6},
There’s one problem with that solution though: we will “recognize” those 0s later on in our iteration and then set their row and column to zero Pretty soon, our entire matrix is 0s!
One way around this is to keep a second matrix which flags the 0 locations We would then do a second pass through the matrix to set the zeros This would take O(MN) space
class Matrix
def initialize(input)
@input = input
@zeros = []
end
def solve
@input.each_with_index do |row, i|
row.each_with_index do |element, j|
@zeros << [i,j] if element == 0
end
end
@zeros.each do |x,y|
set_h_zero(x)
set_v_zero(y)
end
@input
end
private
def set_h_zero(row)
@input[row].map!{0}
end
def set_v_zero(col)
@input.size.times do |r|
@input[r][col] = 0
end
end
end