LeetCode 542 - 01 Matrix

https://leetcode.com/problems/01-matrix/

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 2: 
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

X. BFS

• We start by adding all the cells with 0s to q.
• Intially, distance for each 0 cell is 0 and distance for each 1 is INT_MAX, which is updated during the BFS.
• Pop the cell from queue, and examine its neighbours. If the new calculated distance for neighbour {i,j} is smaller, we add {i,j} to q and update dist[i][j].

https://www.jianshu.com/p/2f8395b06fcf

很自然想到BFS：假如我们把所有的0放入一个双端队列（以下简称DQ），那么再遍历里面元素相邻的4格，然后依此类推即可。
那么最大的问题就是，如何避免重复遍历呢？
暴力的方法就是进入DQ前检查元素是否已经在DQ里面了，当然不推荐，因为效率太低。
另一个靠谱一点的方法就是做标记，用一个flag矩阵来记录进入DQ的元素坐标。
不过如果稍加深入地思考，就会发现其实不用这样。
首先，结果是可以用初始矩阵的，不用重新生成一个，节约空间。
这样的话，为了避免原来的1对后来的结果造成影响，我们需要对其进行处理。好在我们原本就需要把所有的0都拿出来，得先遍历一遍矩阵，所以可以顺带把原来的1变成float('inf')。
因为我们是广度遍历搜索BFS，所以第一遍搜0，第二遍遍历所有0相邻的非0元素，它们的距离不可能大于1。得益于把所有原来的1变成float('inf')，当我们看到某个元素现在是1的时候，我们就知道它已经被算过了。而且这一圈值都是1，也无所谓需要算多次，一次有效的就够了。
同理，第三遍的时候DQ里面放的就是上一次值为1的元素，其相邻元素值可能为0，1，2（过程中），float('inf')，我们当然只关心最后一个了。
也就是说，在改变了原来的值的情况下，在计算m[i][j]相邻元素x的时候，假如x的值小于或者等于m[i][j] + 1，x肯定已经被遍历过了。

简而言之，由于BFS与距离的特性，初始化（1换成无限大）之后所有非0元素只需要一次有效计算就是正确的距离。

换而言之，算过的，不是无限大的，就是遍历过的了。这样就解决了重复遍历的问题。

http://xinglunote.blogspot.com/2017/04/leetcode-542-01-matrix.html

Solution 1: breadth-first search. This will have exceed time limitation problem, because there are many redundant search beginning at each cell of one. Check on the second solution. 276 ms, 26%.

Solution 2: Instead of for each cell, do a breadth-first search. Actually, we only need to update its neighbors (no need to continue searching for all the neighbors of neighbors for that cell). Only need to check the immediate neighbors. 

https://seagullbird.xyz/posts/leetcode-542/
# 是否能够做完这件事？即是否能够覆盖到所有的 1 并且给它们以正确的距离值？ # 答： # 1. 能否覆盖完全？ # 每一次找的都是比自己到 0 的距离大的点， # 这些点之前不可能找过，因为已经找过的点到 0 的距离都比自己到 0 的距离小，所以不会出现重复找点， # 既然不会重复找点，点的数量又是有限值，那一定会找到所有的点； # 2. 能否结果正确？ # 首先确定，第 n 层和第 n-1 层之间到 0 的最短距离只相差 1 # 所以，第 n 层的结果是否正确完全取决于第 n-1 层的结果是否正确 # 所以取决于第一层的结果是否正确 => 显然正确
https://discuss.leetcode.com/topic/83453/java-solution-bfs

General idea is BFS. Some small tricks:

1. At beginning, set cell value to Integer.MAX_VALUE if it is not 0.
2. If newly calculated distance >= current distance, then we don't need to explore that cell again.

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        int m = matrix.size();
        int n = matrix.get(0).size();
        
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix.get(i).get(j) == 0) {
                    queue.offer(new int[] {i, j});
                }
                else {
                    matrix.get(i).set(j, Integer.MAX_VALUE);
                }
            }
        }
        
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || 
                    matrix.get(r).get(c) <= matrix.get(cell[0]).get(cell[1]) + 1) continue;
                queue.add(new int[] {r, c});
                matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
            }
        }
        
        return matrix;
    }

X. DFS
https://leetcode.com/problems/01-matrix/discuss/101060/Java-DFS-solution-beat-95

Using DFS method.

1. Assigned a large value to all the positions with value 1 and don't have 0 neighbors
2. Start dfs search from positions whose value is 1

    public int[][] updateMatrix(int[][] matrix) {
        if(matrix.length==0) return matrix;
        
        for(int i = 0; i<matrix.length; i++)
            for(int j = 0; j<matrix[0].length; j++)
                if(matrix[i][j]==1&&!hasNeiberZero(i, j,matrix)) 
                    matrix[i][j] = matrix.length+matrix[0].length+1;
        
        for(int i = 0; i<matrix.length; i++)
            for(int j = 0; j<matrix[0].length; j++)
                if(matrix[i][j]==1)
                    dfs(matrix, i, j, 1);
        
        return matrix;
    }
    private void dfs(int[][] matrix, int x, int y, int val){
        if(x<0||y<0||y>=matrix[0].length||x>=matrix.length||(matrix[x][y]<=val && val != 1))
            return;

        matrix[x][y] = val;
        
        dfs(matrix, x+1, y, matrix[x][y]+1);
        dfs(matrix, x-1, y, matrix[x][y]+1);
        dfs(matrix, x, y+1, matrix[x][y]+1);
        dfs(matrix, x, y-1, matrix[x][y]+1);
        
    }
    private boolean hasNeiberZero(int x, int y, int[][] matrix){
        if(x>0&&matrix[x-1][y]==0) return true;
        if(x<matrix.length-1&&matrix[x+1][y]==0) return true;
        if(y>0&&matrix[x][y-1]==0) return true;
        if(y<matrix[0].length-1&&matrix[x][y+1]==0) return true;
        
        return false;
    }

X. DP
https://www.jianshu.com/p/2f8395b06fcf

说是DP，其实本质还是距离+1那一套，只不过分成了两遍扫描，第一遍看左边和上边，第二遍看右边和下边。这里需要注意一下扫描方向，第一遍是横向正向扫描，确保左边和上边的已经被扫过，也就是说有0的话也会正确计算，至于0前面的就在下一次扫描里面算。第二遍类似。
这样每个元素都检查了四个方向，虽然分成两部分，但是这两部分互不干涉。
严格的数学证明估计是没有的，不过无论从直觉还是结果来看，这个算法都是正确的。
再往前一步，既然可以分成两部分，那分成四部分，分别的四个方向呢？答案是也可以。

def updateMatrix(self, matrix):
    answer = [[10000 * x for x in row] for row in matrix]
    for _ in range(4):
        for row in answer:
            for j in range(1, len(row)):
                row[j] = min(row[j], row[j-1] + 1)
        answer = map(list, zip(*answer[::-1]))
    return answer

这个答案更加短小精悍。
answer = [[10000 * x for x in row] for row in matrix]这句代码是将矩阵进行初始化，不过因为float('inf')*0=nan即Not a number，这里选择10000来当乘数，因为根据题意距离总是会小于10000的。
对于每一行从左向右，计算左边一格+1。方向的原理和DP解法类似，左边的是已经遍历过的所以拿过来计算。
然后把矩阵转置。重复4次。
这样虽然每次计算都是向右，但是矩阵在转，转了一圈就相当于计算了四个方向。

http://www.cnblogs.com/grandyang/p/6602288.html
下面这种解法是参考的qswawrq大神的帖子，他想出了一种二次扫描的解法，从而不用使用BFS了。这种解法也相当的巧妙，我们首先建立一个和matrix大小相等的矩阵res，初始化为很大的值，这里我们用INT_MAX-1，为甚么要减1呢，后面再说。然后我们遍历matrix矩阵，当遇到为0的位置，我们将结果res矩阵的对应位置也设为0，这make sense吧，就不多说了。然后就是这个解法的精髓了，如果不是0的地方，我们在第一次扫描的时候，比较其左边和上边的位置，取其中较小的值，再加上1，来更新结果res中的对应位置。这里就明白了为啥我们要初始化为INT_MAX-1了吧，因为这里要加1，如果初始化为INT_MAX就会整型溢出，不过放心，由于是取较小值，res[i][j]永远不会取到INT_MAX，所以不会有再加1溢出的风险。第一次遍历我们比较了左和上的方向，那么我们第二次遍历就要比较右和下的方向，注意两种情况下我们不需要比较，一种是当值为0时，还有一种是当值为1时，这两种情况下值都不可能再变小了，所以没有更新的必要

在史蒂芬大神的帖子中，他提出了一种变型的方法，没有再区分左上右下，而是每次都跟左边相比，但是需要每次把矩阵旋转90度。他用python写的解法异常的简洁，貌似python中可以一行代码进行矩阵旋转，但是貌似C++没有这么叼，矩阵旋转写起来还是需要两个for循环，写出来估计也不短
https://leetcode.com/articles/01-matrix/

The distance of a cell from 0 can be calculated if we know the nearest distance for all the neighbours, in which case the distance is minimum distance of any neightbour + 1. And, instantly, the word come to mind DP!!
For each 1, the minimum path to 0 can be in any direction. So, we need to check all the 4 direction. In one iteration from top to bottom, we can check left and top directions, and we need another iteration from bottom to top to check for right and bottom direction.

Algorithm

• Iterate the matrix from top to bottom-left to right:
• Update $\text{dist}[i][j]=\min(\text{dist}[i][j],\min(\text{dist}[i][j-1],\text{dist}[i-1][j])+1)$ i.e., minimum of the current dist and distance from top or left neighbour +1, that would have been already calculated previously in the current iteration.
• Now, we need to do the back iteration in the similar manner: from bottom to top-right to left:
• Update $\text{dist}[i][j]=\min(\text{dist}[i][j],\min(\text{dist}[i][j+1],\text{dist}[i+1][j])+1)$ i.e. minimum of current dist and distances calculated from bottom and right neighbours, that would be already available in current iteration.

https://discuss.leetcode.com/topic/83558/java-33ms-solution-with-two-sweeps-in-o-n

In the first sweep, we visit each entry in natural order and answer[i][j] = min(Integer.MAX_VALUE, min(answer[i - 1][j], answer[i][j - 1]) + 1).
in the second sweep, we visit each entry in reverse order and answer[i][j] = min(answer[i][j], min(answer[i + 1][j], answer[i][j + 1]) + 1).

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        if (matrix.size() == 0 || matrix.get(0).size() == 0)
            return matrix;
        int M = matrix.size(), N = matrix.get(0).size();
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++) {
                if (matrix.get(i).get(j) == 0)
                    continue;
                int val = Integer.MAX_VALUE - 1;
                if (i > 0)
                    val = Math.min(val, matrix.get(i - 1).get(j) + 1);
                if (j > 0)
                    val = Math.min(val, matrix.get(i).get(j - 1) + 1);
                matrix.get(i).set(j, val);
            }

        for (int i = M - 1; i >= 0; i--)
            for (int j = N - 1; j >= 0; j--) {
                if (matrix.get(i).get(j) == 0)
                    continue;
                int val = matrix.get(i).get(j);
                if (i < M - 1)
                    val = Math.min(val, matrix.get(i + 1).get(j) + 1);
                if (j < N - 1)
                    val = Math.min(val, matrix.get(i).get(j + 1) + 1);
                matrix.get(i).set(j, val);
            }
        return matrix;
    }

Just another variation, first doing rows and then doing columns. This way I don't need the "if valid neighbor" checks, I can just start the loops from 1 instead of 0.

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        this.matrix = matrix;
        m = matrix.size();
        n = matrix.get(0).size();
        for (List<Integer> row : matrix)
            for (int j = 0; j < n; j++)
                row.set(j, row.get(j) * 10000);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                relax(i, j, i, j-1);
                relax(i, n-1-j, i, n-j);
                relax(i, j, i-1, j);
                relax(m-1-i, j, m-i, j);
            }
        }
        return matrix;
    }
    void relax(int i, int j, int i0, int j0) {
        if (i0 >= 0 && i0 < m && j0 >= 0 && j0 < n)
            matrix.get(i).set(j, Math.min(matrix.get(i).get(j), matrix.get(i0).get(j0) + 1));
    }
    List<List<Integer>> matrix;
    int m, n;

X. DP
https://leetcode.com/problems/01-matrix/discuss/101051/Simple-Java-solution-beat-99-(use-DP)


https://discuss.leetcode.com/topic/83574/short-solution-each-path-needs-at-most-one-turn

def updateMatrix(self, matrix):
    answer = [[10000 * x for x in row] for row in matrix]
    for _ in range(4):
        for row in answer:
            for j in range(1, len(row)):
                row[j] = min(row[j], row[j-1] + 1)
        answer = map(list, zip(*answer[::-1]))
    return answer

Based on @qswawrq's solution which only considers down/right paths (meaning a combination of only down and right moves, from some 0 to some 1) and up/left paths. When I realized why that works, I realized that we don't even need paths like down,right,down,right. We can instead go just down,down,right,right or right,right,down,down. Just one turn (change of direction). It's the same length, and all of the intermediate cells must be 1 because otherwise down,right,down,right wouldn't have been an optimal path in the first place.

So in my solution I simply optimize in each direction, one after the other. For this I "optimize rightwards" and "rotate the matrix by 90 degrees" four times. Then I have covered every pair of directions, which is enough to cover every straight path and every single-turn path.

X. https://leetcode.com/articles/01-matrix/

• Initialize dist[i][j]=INT_MAX for all {i,j} cells.
• Iterate over the matrix.
• If cell is 0, dist[i][j]=0,
• Else, for each 1 cell,
• Iterate over the entire matrix
• If the cell is 0, calculate its distance from current cell as abs(k-i)+abs(l-j).
• If the distance is smaller than the current distance, update it.

• Time complexity: $O((r \cdot c)^2)$. Iterating over the entire matrix for each 1 in the matrix.
• Space complexity: $O(r \cdot c)$. No extra space required than the vector<vector<int> > dist

vector<vector<int> > updateMatrix(vector<vector<int> >& matrix)
{
    int rows = matrix.size();
    if (rows == 0)
        return matrix;
    int cols = matrix[0].size();
    vector<vector<int> > dist(rows, vector<int>(cols, INT_MAX));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 0)
                dist[i][j] = 0;
            else {
                for (int k = 0; k < rows; k++)
                    for (int l = 0; l < cols; l++)
                        if (matrix[k][l] == 0) {
                            int dist_01 = abs(k - i) + abs(l - j);
                            dist[i][j] = min(dist[i][j], abs(k - i) + abs(l - j));
                        }
            }
        }
    }
    return dist;
}

X. Inefficient, dfs for each cell
https://www.acwing.com/activity/content/code/content/10822/

https://leetcode.com/problems/01-matrix/discuss/101036/java-o1-space-omnk-time-simple-solution-and-explanation-beats-97