Neat Java BFS Solution - 19ms


  • 0
    F
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    	int min = Integer.MAX_VALUE;
    	int m = maze.length;
    	int n = maze[0].length;
    	int[][] visited = new int[m][n];
    	for(int i=0;i<m;i++){
    		for(int j=0;j<n;j++){
    			visited[i][j]=Integer.MAX_VALUE;
    		}
    	}
    	visited[start[0]][start[1]] = 0;
    	Queue<Integer> queue = new LinkedList<>();
    	queue.offer(start[0] * n + start[1]);
    	while (!queue.isEmpty()) {
    		int index = queue.poll();
    		int x = index / n;
    		int y = index % n;
    		if (x == destination[0] && y == destination[1])
    			min = Math.min(min, visited[x][y]);
    
    		int i = x;
    		while (i >= 0 && maze[i][y] == 0) {
    			i--;
    		}
    		i++;
    		if (visited[x][y] + x - i < visited[i][y]) {
    			queue.offer(i * n + y);
    			visited[i][y] = visited[x][y] + x - i;
    		}
    
    		i = x;
    		while (i < m && maze[i][y] == 0) {
    			i++;
    		}
    		i--;
    		if (visited[x][y] + i - x < visited[i][y]) {
    			queue.offer(i * n + y);
    			visited[i][y] = visited[x][y] + i - x;
    		}
    
    		int j = y;
    		while (j >= 0 && maze[x][j] == 0) {
    			j--;
    		}
    		j++;
    		if (visited[x][y] + y - j < visited[x][j]) {
    			queue.offer(x * n + j);
    			visited[x][j] = visited[x][y] + y - j;
    		}
    
    		j = y;
    		while (j < n && maze[x][j] == 0) {
    			j++;
    		}
    		j--;
    		if (visited[x][y] + j - y < visited[x][j]) {
    			queue.offer(x * n + j);
    			visited[x][j] = visited[x][y] + j - y;
    		}
    	}
    
    	return min==Integer.MAX_VALUE?-1:min;
    }

Log in to reply
 

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