## Monday, January 25, 2016

### 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``;`

`    ``}`