CC150 1.7

1_7.cpp

/* CC150 1.7
 * Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
 */

#include <iostream>
#include <vector>

using namespace std;

void setZeros(vector<vector<int>> &mat)
{
	int M = mat.size(), N = mat[0].size();
	if (M < 1 || N < 1)
		return;
	vector<int> rowZeros, colZeros; // hold the row and column indices of zero elements
	for (int i = 0; i < M; ++i) { // search zeros by row
		for (int j = 0; j < N; ++j) {
			if (mat[i][j] == 0) { // mark row index when first see a zero
				rowZeros.push_back(i);
				break; // skip the rest of this row and continue search the next row
			}
		}
	}
	for (int j = 0; j < N; ++j) { // search zeros by column, so that colZeros is also in ascending order
		for (int i = 0; i < M; ++i) {
			if (mat[i][j] == 0) {
				colZeros.push_back(j);
				break;
			}
		}
	}
	// set rows to zero
	for (vector<int>::size_type k = 0; k < rowZeros.size(); ++k) {
		for (int j = 0; j < N; ++j)
			mat[rowZeros[k]][j] = 0;
	}
	// set columns to zero
	for (vector<int>::size_type k = 0; k < colZeros.size(); ++k) {
		for (int i = 0; i < M; ++i)
			mat[i][colZeros[k]] = 0;
	}
	return;
}

void setZeros2(vector<vector<int>> &mat)
{
	int M = mat.size(), N = mat[0].size();
	if (M < 2 && N < 2)
		return;
	bool rowHasZero = false, colHasZero = false;
	for (int j = 0; j < N; ++j) { // scan first row for zeros, set rowHasZero
		if (mat[0][j] == 0) {
			rowHasZero = true;
			break;
		}
	}
	for (int i = 0; i < M; ++i) { // scan first column for zeros, set colHasZero
		if (mat[i][0] == 0) {
			colHasZero = true;
			break;
		}
	}
	for (int i = 0; i < M; ++i) { // only need one scan since we don't need to keep indices in order as before
		for (int j = 0; j < N; ++j) {
			if (mat[i][j] == 0) {
				mat[i][0] = 0;
				mat[0][j] = 0;
			}
		}
	}
	// set rows and columns to zero according to flags
	// NOTE: SKIP THE FIRST ROW AND COLUMN FOR NOW! OR YOU'LL GET A ZERO METRIX!
	for (int i = 1; i < M; ++i) {
		for (int j = 1; j < N; ++j) {
			if (mat[i][0] == 0 || mat[0][j] == 0)
				mat[i][j] = 0;
		}
	}
	// set first row to zero if rowHasZero indicates so
	if (rowHasZero) {
		for (int j = 0; j < N; ++j)
			mat[0][j] = 0;
	}
	// set first column to zero if colHasZero indicates so
	if (colHasZero) {
		for (int i = 0; i < M; ++i)
			mat[i][0] = 0;
	}
	return;
}

int main()
{
	int M, N;
	cin >> M >> N;
	vector<vector<int>> matrix;
	for (int i = 0; i < M; ++i) {
		vector<int> row;
		for (int j = 0; j < N; ++j) {
			int temp;
			cin >> temp;
			row.push_back(temp);
		}
		matrix.push_back(row);
	}
	setZeros(matrix);
	for (auto &row : matrix) {
		for (auto &col : row)
			cout << col << "\t";
		cout << endl;
	}
	return 0;
}