Fast O(m*n) BFS solution with deque


  • 0
    L
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    	int rows = maze.length;
    	int cols = 0;
    	if (rows > 0) {
    		cols = maze[0].length;
    	}
    	boolean[][][] visited = new boolean[rows][cols][4];
    	Deque<int[]> deque = new ArrayDeque<>();
    	int[][] dirs = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
    	//store visited for each direction.
    	for (int i = 0; i < dirs.length; i++) {
    		deque.offer(new int[] { start[0], start[1], 0, i });
    		visited[start[0]][start[1]][i] = true;
    	}
    	while (!deque.isEmpty()) {
    		int[] prev = deque.poll();
    		int row = prev[0];
    		int col = prev[1];
    		int dis = prev[2];
    		int[] dir = dirs[prev[3]];
    		if (row + dir[0] >= 0 && col + dir[1] >= 0 && row + dir[0] < rows && col + dir[1] < cols
    				&& maze[row + dir[0]][col + dir[1]] == 0) {
    			//not changing direction
    			row += dir[0];
    			col += dir[1];
    			if (!visited[row][col][prev[3]]) {
    				deque.offer(new int[] { row, col, dis + 1, prev[3] });
    				visited[row][col][prev[3]] = true;
    			}
    		} else {
    			//changing direction
    			if (row == destination[0] && col == destination[1]) {
    				return dis;
    			}
    			for (int i = 0; i < dirs.length; i++) {
    				if (!visited[row][col][i]) {
    					//push to deque since distance does not change
    					deque.push(new int[] { row, col, dis, i });
    					visited[row][col][i] = true;
    				}
    			}
    		}
    	}
    	return -1;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.