Wednesday, January 20, 2016

Twitter: Min Distance between two nodes

Given a 2D m*n board, 0 means an empty space we can pass, and 1 means it is a block we cannot pass. 

Give a starting and ending point, find out the min distance we can walk from one point to another. We can move up, down, left and right. 

Return the min distance between two nodes. If we can never reach, return -1.

For example,
0 0 0 0 
S 0 0 0 
0 0 0 E
return 4

0 0 0 0 
S 1 1 0
0 0 1 E
return 6, because the path is
0 - 0 - 0 - 0
|               |
S   1   1   0 
                |
0    0   1   E

Understand the problem:
Use BFS, traverse the matrix layer by layer, until we reach the ending point. 


Code (Java):
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */
public class Solution {
    private int minDistance = 0;
    public int findMinDistance(int[][] board, int startX, int startY, int endX, int endY) {
        if (board == null || board.length == 0) {
            return -1;
        }
        
        // 0 - open
        // 1 - block 
        int m = board.length;
        int n = board[0].length;
        
        boolean[][] visited = new boolean[m][n];
        Queue<Integer> queue = new LinkedList<>();
        
        if (findMinDistanceHelper(board, startX, startY, endX, endY, visited, queue) == false) {
            return -1;
        } else {
            return minDistance;
        }
    }
    
    private boolean findMinDistanceHelper(int[][] board, int startX, int startY, 
                                          int endX, int endY,
                                          boolean[][] visited, Queue<Integer> queue) {
        if (fill(board, startX, startY, endX, endY, visited, queue) == true) {
            return true;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        while (!queue.isEmpty()) {
            minDistance++;
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                int cord = queue.poll();
                int x = cord / n;
                int y = cord % n;
                boolean ans = fill(board, x, y - 1, endX, endY, visited, queue);
                ans |= fill(board, x, y + 1, endX, endY, visited, queue);
                ans |= fill(board, x - 1, y, endX, endY, visited, queue);
                ans |= fill(board, x + 1, y, endX, endY, visited, queue);
            
                if (ans) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean fill(int[][] board, int curX, int curY, int endX, int endY, 
                         boolean[][] visited, Queue<Integer> queue) {
        int m = board.length;
        int n = board[0].length;
        
        if (curX < 0 || curX >= m || curY < 0 || curY >= n || visited[curX][curY]) {
            return false;
        }
        
        if (board[curX][curY] == 1) {
            return false;
        }
        
        if (curX == endX && curY == endY) {
            return true;
        }
        
        visited[curX][curY] = true;
        queue.offer(curX * n + curY);
        
        return false;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] board = new int[][]{{1, 0, 0, 0}, 
                                    {0, 1, 1, 0},
                                    {1, 0, 1, 0}};
        
        int startX = 1;
        int startY = 0;
        int endX = 2;
        int endY = 3;
        
        int result = sol.findMinDistance(board, startX, startY, endX, endY);
        
        System.out.println(result);
    }
}

No comments:

Post a Comment