Zenefits Interview - Minimum distance to guarded rooms - 我的博客 - ITeye技术网站

Zenefits Interview - Minimum distance to guarded rooms - 我的博客 - ITeye技术网站
求每个元素到guaraded room的最短距离
0: closed room
1: open room
2: guarded room
例如input
1 2 1
1 0 1
1 2 1
那么output是
1 0  1.
2 -1 2
1 0  1

1. private static int[][] dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};  
2. public static void minDistance(int[][] R) {  
3.     Queue<Integer> queue = new LinkedList<>();  
4.     int m = R.length, n = R[0].length;  
5.     for(int i=0; i<m; i++) {  
6.         for(int j=0; j<n; j++) {  
7.             if(R[i][j] == 2) {  
8.                 queue.offer(i*n+j);  
9.             }  
10.         }  
11.     }  
12.     int OFFSET = 10;  
13.     while(!queue.isEmpty()) {  
14.         int val = queue.poll();  
15.         int r = val / n;  
16.         int c = val % n;  
17.         for(int k=0; k<dir.length; k++) {  
18.             int i = dir[k][0] + r;  
19.             int j = dir[k][1] + c;  
20.             if(i>=0 && i<m && j>=0 && j<n && R[i][j] == 1) {  
21.                 R[i][j] = R[r][c] == 2 ? OFFSET+1 : R[r][c]+1;  
22.                 queue.offer(i*n+j);  
23.             }  
24.         }  
25.     }  
26.     for(int i=0; i<m; i++) {  
27.         for(int j=0; j<n; j++) {  
28.             if(R[i][j] == 2) {  
29.                 R[i][j] = 0;  
30.             } else if(R[i][j] == 0) {  
31.                 R[i][j] = -1;  
32.             } else {  
33.                 R[i][j] -= OFFSET;  
34.             }  
35.         }  
36.     }  
37. }  

http://buttercola.blogspot.com/2015/11/zenefits-minimum-distance-to-guarded.html
We can first pre-process the input matrix, where change 
2 -> 0, because distance from guarded room itself is 0.
1 -> MAX, means the distance to the guarded room is MAX
0 -> -1, means the distance is -1 to the guarded room.

    public void wallsAndGates(int[][] rooms) {

        if (rooms == null || rooms.length == 0) {

            return;

        }

         

        int m = rooms.length;

        int n = rooms[0].length;

         

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (rooms[i][j] == 0) {

                    wallsAndGatesHelper(i, j, 0, rooms, queue);

                }

            }

        }

    }

     

    private void wallsAndGatesHelper(int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {

        fill(row, col, distance, rooms, queue);

         

        int m = rooms.length;

        int n = rooms[0].length;

         

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i = 0; i < size; i++) {

                int cord = queue.poll();

                int x = cord / n;

                int y = cord % n;

             

                fill(x - 1, y, distance + 1, rooms, queue);

                fill(x + 1, y, distance + 1, rooms, queue);

                fill(x, y - 1, distance + 1, rooms, queue);

                fill(x, y + 1, distance + 1, rooms, queue);

             

            }

            distance++;

        }

    }

     

    private void fill (int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {

        int m = rooms.length;

        int n = rooms[0].length;

         

        if (row < 0 || row >= m || col < 0 || col >= n) {

            return;

        }

         

        if (rooms[row][col] == -1) {

            return;

        }

         

        if (distance > rooms[row][col]) {

            return;

        }

         

        if (distance < rooms[row][col]) {

            rooms[row][col] = distance;

        }

         

        int cord = row * n + col;

        queue.offer(cord);

    }

Then the entire problem is the same as the Leetcode Walls and Gates
Related: [LeetCode] Walls and Gates
Read full article from Zenefits Interview - Minimum distance to guarded rooms - 我的博客 - ITeye技术网站