01 Matrix

Leave a comment

June 20, 2017 by oneOokay

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 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

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.

DP和BFS. 不知道为什么不是很能理解这题的BFS解法,非要走一遍才弄清楚.

DFS…..TODO

想到了DP,但是自我否定了因为用dp的话推导过程要同时向上下左右四个方向推导,不行,因为dp是建立在前一步的值都已经处理过的情况下的.

  1. 其实是可以用dp的,只不过要分两步走,就可以了
    1. 第一个从左上角开始,对一个点的上和左元素进行判断.
    2. 第一个从右下角开始,对一个点的下和右进行判断.
  2. 要注意的是:’1’的初始值.
    1. 最好不用Integer.MAX_VALUE:因为在代码里面要根据dp[][]的值+1,这样容易overflow(当然可以用Integer.MAX_VALUE – 1,但是我觉得是个hack)
    2. 我觉得最好的值是用row + col:因为是一个manhattan distance,最大值就是row + col.
  3. 在扫描推导过程中注意是based on dp[][]还是之前的matrix.
public int[][] updateMatrix(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return M;
        int row = M.length, col = M[0].length;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i ++){
            for (int j = 0; j < col; j ++){
                if (M[i][j] == 1){
                    dp[i][j] = row + col; 
            }
        }
        
        for (int i = 0; i < row; i ++){
            for (int j = 0; j < col; j ++){                  if (dp[i][j] == 0) continue;                  int top = i - 1 >= 0 ? dp[i - 1][j] : dp[i][j];
                int left = j - 1 >= 0 ? dp[i][j - 1] : dp[i][j];
//这里一定要也对dp[i][j]自身的值进行比较.以及不要忘了对top和left的最小值+1
                dp[i][j] = Math.min(dp[i][j], Math.min(top, left) + 1);
            }
        }
        
        for (int i = row - 1; i >= 0; i --){
            for (int j = col - 1; j >= 0; j --){
                if (dp[i][j] == 0) continue;
                int bottom = i + 1 < row ? dp[i + 1][j] : dp[i][j];
                int right = j + 1 < col ? dp[i][j + 1] : dp[i][j];
                dp[i][j] = Math.min(dp[i][j], Math.min(bottom, right) + 1);
            }
        }
        return dp;
    }

BFS:

对什么进行BFS?值为0的还是值为1的?

  • 把值为0的cell放到queue里面,即先对所有的0进行BFS
  • 再把BFS中值变换了的cell放入queue.

怎么BSF?

  • 从queue里面pull出一个cell之后,对这个当前的cell进行上下左右“一步走”即可.
  • 即仅对当前cell的上下左右四个cell的值和当前cell的值+1的大小进行判断.
  • 如果上下左右四个cell的值被更新了,把被更新的cell也加入到queueu里面.
public int[][] updateMatrix(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0) return M;
        int row = M.length, col = M[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; i ++){
            for (int j = 0; j < col; j ++){
//把'1'初始化为row + col;把值为0的cell加入到queue里面.
                if (M[i][j] != 0) M[i][j] = row + col;
                else {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()){
            int[] cell = queue.poll();
            int value = M[cell[0]][cell[1]];
            for(int[] dir : dirs){
                int r = cell[0] + dir[0];
                int c = cell[1] + dir[1];
//如果上下左右cell的值比value+1还小,不需要更新,不需要加入queue里面
                if (r < 0 || r >= row || c < 0 || c >= col ||
                M[r][c] <= value + 1) continue; 
                M[r][c] = value + 1;//更新值
                queue.offer(new int[]{r, c});//加入queue
            }
        }
        return M;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: