Установите каждую ячейку в матрице в 0, если эта строка или столбец содержит 0

Question

Учитывая матрицу NxN с 0 и 1. Установите каждую строку, содержащую 0, для всех 0 с и установите каждый столбец, содержащий 0, для всех 0 с.

Например

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

Результаты в

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

Инженер Microsoft сказал мне, что существует решение, не требующее дополнительной памяти, только две логические переменные и один проход, поэтому я ищу этот ответ.

Кстати, представьте, что это битовая матрица, поэтому в матрице допускается только 1 и 0.

Answer 1

Хорошо, я понимаю, что это не совсем совпадает, но я получил его за один проход, используя bool и байт вместо двух bools ... close. Я бы также не ручался за его эффективность, но такие вопросы часто требуют неоптимальных решений.

private static void doIt(byte[,] matrix)
{
    byte zeroCols = 0;
    bool zeroRow = false;

    for (int row = 0; row <= matrix.GetUpperBound(0); row++)
    {
        zeroRow = false;
        for (int col = 0; col <= matrix.GetUpperBound(1); col++)
        {
            if (matrix[row, col] == 0)
            {

                zeroRow = true;
                zeroCols |= (byte)(Math.Pow(2, col));

                // reset this column in previous rows
                for (int innerRow = 0; innerRow < row; innerRow++)
                {
                    matrix[innerRow, col] = 0;
                }

                // reset the previous columns in this row
                for (int innerCol = 0; innerCol < col; innerCol++)
                {
                    matrix[row, innerCol] = 0;
                }
            }
            else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0)
            {
                matrix[row, col] = 0;
            }

            // Force the row to zero
            if (zeroRow) { matrix[row, col] = 0; }
        }
    }
}