Google Interview - Perimeter of region that has the same color of that point - 我的博客 - ITeye技术网站

Google Interview - Perimeter of region that has the same color of that point - 我的博客 - ITeye技术网站
given grid of colors, coordinate of a point and its color, find the perimeter of the region that has the same color of that point.
BFS或DFS，构成perimeter的条件是只要上下左右有一个不是同颜色或者是out of bound 用一个set记录visit的信息

1. public static class Point{  
2.     int r, c;  
3.     public Point(int x, int y) {r = x; c = y;}  
4.     public int hashCode() {return r*31+c; }  
5. }  
6. private static final int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};  
7. public static int findPerimeter(int[][] mat, int r, int c) {  
8.     int m = mat.length, n = mat[0].length;  
9.     boolean[][] visited = new boolean[m][n];  
10.     int cnt = 0;  
11.     Queue<Point> q = new LinkedList<>();  
12.     q.offer(new Point(r,c));  
13.     while(!q.isEmpty()) {  
14.         Point p = q.poll();  
15.         if(visited[p.r][p.c]) continue;  
16.         visited[p.r][p.c] = true;  
17.         boolean isEdge = false;  
18.         for(int[] dir: dirs) {  
19.             int i = p.r+dir[0], j = p.c+dir[1];  
20.             if(i<0||j<0||i>=m||j>=n||mat[p.r][p.c]!=mat[i][j]) {  
21.                 isEdge = true;  
22.             } else {  
23.                 q.offer(new Point(i,j));  
24.             }  
25.         }  
26.         if(isEdge) cnt++;  
27.     }  
28.     return cnt;  
29. }  
30. public static void main (String[] args) {  
31.     int[][] mat = { {1,1,2,2,3,4,5},  
32.                     {1,1,1,1,1,4,5},  
33.                     {1,1,1,1,1,4,5},  
34.                     {1,1,2,2,3,4,5}};  
35.     System.out.println(findPerimeter(mat, 2, 1));  
36. }  

Read full article from Google Interview - Perimeter of region that has the same color of that point - 我的博客 - ITeye技术网站