LeetCode Q 542 - 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 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:

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

Solution : BFS / DP

Solution 1: BFS

Steps:
We regard the 2D matrix as a string. For an element in the matrix, we use rowNum * colLength + colNum to denote its index.

push the 0s in the matrix to the queue.
do the bfs, at each level
- pull the index from the queue. According to that index, we can determine the rowNumber and colNumber.
- we traverse its left, right, up and down, if they haven’t been visited, then we offer them in the queue and visited set.
- when we have finished traversing one layer, we increase the level.

Code:

public int openLock(String[] deadends, String target) {
	
	Set<String> deadSet = new HashSet<>();
	for (String str : deadends) deadSet.add(str);
	
	if (deadSet.contains(target) || deadSet.contains("0000")) return -1;
	
	Queue<String> queA = new LinkedList<>();
	Set<String> visitedA = new HashSet<>();
	queA.offer("0000");
	visitedA.add("0000");
	
	Queue<String> queB = new LinkedList<>();
	Set<String> visitedB = new HashSet<>();
	queB.offer(target);
	visitedB.add(target);
	
	Queue<String> que = null; 
	Set<String> setCurr = null; 
	Set<String> setOp = null;
	
	int result = 0;
	while (!queA.isEmpty() && !queB.isEmpty()) {
		if (queA.size() <= queB.size()) {
			que = queA; setCurr = visitedA; setOp = visitedB;
		} else {
			que = queB; setCurr = visitedB; setOp = visitedA;
		}
		
		result++;
		int size = que.size();
		while (size-- != 0) {
			
			String cur = que.poll();
			
			for (int i = 0; i < 4; ++i) {
				char[] chs = cur.toCharArray();
				
				chs[i] = (char)((cur.charAt(i) - '0' + 9) % 10 + '0');
				String next = String.valueOf(chs);
				if (setOp.contains(next)) return result;
				if (!setCurr.contains(next) && !deadSet.contains(next)) {
					que.offer(next); setCurr.add(next);
				}
				
				chs[i] = (char)((cur.charAt(i) - '0' + 1) % 10 + '0');
				next = String.valueOf(chs);
				if (setOp.contains(next)) return result;
				if (!setCurr.contains(next) && !deadSet.contains(next)) {
					que.offer(next); setCurr.add(next);
				}
			}
		}
	}
	
	return -1;
}

A Better Solution: DP

States: dp[i][j] the min distance of number at row i and col j.
State Transfer Function:
- Iterate the matrix from top left to bottom right:
  Update dp[i][j] = min(dp[i][j], min(dp[i][j - 1], dp[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.
- Do the back iteration in the similar manner: from bottom right to top left:
  Update dp[i][j] = min(dp[i][j], min(dp[i][j + 1], dp[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.

Code:

public int[][] updateMatrix(int[][] matrix) {
	if (matrix == null || matrix.length == 0) return matrix;
	
	int R = matrix.length, C = matrix[0].length;
	
	int[][] dp = new int[R][C];
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			if (matrix[i][j] == 0) dp[i][j] = 0;
			else dp[i][j] = 1000000;
			if (i > 0) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
			if (j > 0) dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
		}
	}
	
	for (int i = R - 1; i >= 0; --i) {
		for (int j = C - 1; j >= 0; --j) {
			if (dp[i][j] > 0) {
				if (i < R - 1) dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
				if (j < C - 1) dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
			}
		}
	}
	return dp;
}

Reprint policy