## Tuesday, December 1, 2015

### Buttercola: Zenefits: Robert Merge Point

Buttercola: Zenefits: Robert Merge Point

*//problem: robot merge point
//input:
//robot: 1
//obstacle: X
[
0   0   0   M   1
0   1   X   0   0
0   X   0   0   0
0   0   0   1   0
0   0   0   0   0
//output:
//best merge point: M
3 + 1 + 3 = 7
. from: 1point3acres.com/bbs
Definition: Best merge point: minimal sum of path num between robots and merge point*/

Solution:

Note that this problem like mini distance can only be solved by using BFS, not DFS.
We need to handle when to mark the visited[][] as false. In this question, we simply that for each tracking, we define a new boolean[][ visited.

`  ``public` `Point findTheBestMergePoint(``char``[][] matrix) {`
`    ``if` `(matrix == ``null` `|| matrix.length == ``0``) {`
`      ``return` `null``;`
`    ``}`
`    `
`    ``int` `m = matrix.length;`
`    ``int` `n = matrix[``0``].length;`
`    `
`    ``int``[][] dist = ``new` `int``[m][n];`
`   `
`    ``Queue<Integer> queue = ``new` `LinkedList<>();`
`    ``// 0 open`
`    ``// 1 robert`
`    ``// X block`
`    `
`    ``for` `(``int` `i = ``0``; i < m; i++) {`
`      ``for` `(``int` `j = ``0``; j < n; j++) {`
`        ``if` `(matrix[i][j] == ``'1'``) {`
`          ``boolean``[][] visited = ``new` `boolean``[m][n];`
`          ``findTheBestMergePointHelper(i, j, matrix, dist, visited, ``0``, queue);`
`        ``}`
`      ``}`
`    ``}`
`    `
`    ``// Step 2: find the shorest distance`
`    ``Point result = ``new` `Point();`
`    ``int` `minDist = Integer.MAX_VALUE;`
`    ``for` `(``int` `i = ``0``; i < m; i++) {`
`      ``for` `(``int` `j = ``0``; j < n; j++) {`
`        ``// Skip the unreachable point`
`        ``if` `((dist[i][j] == ``0` `&& matrix[i][j] == ``'0'``) || `
`            ``matrix[i][j] == ``'X'``) {`
`          ``continue``;`
`        ``}`
`        `
`        ``if` `(dist[i][j] < minDist) {`
`          ``minDist = dist[i][j];`
`          ``result.x = i;`
`          ``result.y = j;`
`        ``}`
`      ``}`
`    ``}`
`    `
`    ``return` `result;`
`  ``}`
`  `
`  ``private` `void` `findTheBestMergePointHelper(``int` `row, ``int` `col, ``char``[][] matrix, `
`                                           ``int``[][] dist, ``boolean``[][] visited, `
`                                           ``int` `distance, Queue<Integer> queue) {`
`    ``int` `m = matrix.length;`
`    ``int` `n = matrix[``0``].length;`
`    `
`    ``fill(row, col, matrix, dist, visited, distance, queue);`
`    `
`    ``while` `(!queue.isEmpty()) {`
`      ``int` `sz = queue.size();`
`      ``for` `(``int` `i = ``0``; i < sz; i++) {`
`        ``int` `cord = queue.poll();`
`        ``int` `x = cord / n;`
`        ``int` `y = cord % n;`
`        `
`        ``fill(row - ``1``, col, matrix, dist, visited, distance + ``1``, queue);`
`        ``fill(row + ``1``, col, matrix, dist, visited, distance + ``1``, queue);`
`        ``fill(row, col - ``1``, matrix, dist, visited, distance + ``1``, queue);`
`        ``fill(row, col + ``1``, matrix, dist, visited, distance + ``1``, queue);`
`      ``}`
`      `
`      ``distance++;`
`    ``}`
`  ``}`
`  `
`  ``private` `void` `fill(``int` `row, ``int` `col, ``char``[][] matrix, `
`                    ``int``[][] dist, ``boolean``[][] visited,`
`                    ``int` `distance, Queue<Integer> queue) {`
`    ``int` `m = matrix.length;`
`    ``int` `n = matrix[``0``].length;`
`    `
`    ``if` `(row < ``0` `|| row >= m || col < ``0` `|| col >= n) {`
`      ``return``;`
`    ``}`
`    `
`    ``if` `(visited[row][col] || matrix[row][col] == ``'X'``) {`
`      ``return``;`
`    ``}`
`    `
`    ``visited[row][col] = ``true``;`
`    `
`    ``dist[row][col] += distance;`
`    `
`    ``queue.offer(row * n + col);`
`  ``}`