Buttercola: Twitter: Min Distance between two nodes

Buttercola: 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. 

    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;

    }

Read full article from Buttercola: Twitter: Min Distance between two nodes