# 【LeetCode】 73. Set Matrix Zeroes

## Description
> Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it [in-place](https://en.wikipedia.org/wiki/In-place_algorithm).

> Follow up:
> * A straight forward solution using O(mn) space is probably a bad idea.
> * A simple improvement uses O(m + n) space, but still not the best solution.
> * Could you devise a constant space solution?

> 給予一個 m x n 的矩陣，如果有一個元素為0，將和它同列、同行的都設成0。用[原地演算法](https://zh.wikipedia.org/wiki/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)完成。

> 進階：
> * 直接使用O(mn)空間複雜度的答案可能是個不好的想法。
> * 一個簡單的進步是使用O(m + n)空間複雜度，但仍然有更好的答案。
> * 你可以在常數空間複雜度中完成嗎？

## Example:

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]


Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

## Solution

* 因為不能使用和`m`、`n`有關的新的記憶體空間，我們直接使用`m[0][j]`來標註哪些橫排要清空，`m[i][0]`來標註哪些直排要清空。
* `m[0][0]`沒辦法同時記錄是直排還是橫排要清空，因此要一個額外`bool`去存。

### Code

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool firstZero = false;
        for(int i = 0; i < matrix.size(); i++)
        {
            firstZero |= !matrix[i][0];
            for(int j = 1; j < matrix[0].size(); j++)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for(int i = 1; i < matrix.size(); i++)
        {
            for(int j = 1; j < matrix[0].size(); j++)
            {
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                {
                    matrix[i][j] = 0;
                }
            }
        }
        
        if(matrix[0][0] == 0)
            for(int j = 0; j < matrix[0].size(); j++)
                matrix[0][j] = 0;
        
        if(firstZero)
            for(int i = 0; i < matrix.size(); i++)
                matrix[i][0] = 0;
        
    }
};

###### tags: `LeetCode` `C++`