Google Interview - Perimeter of region that has the same color of that point

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的信息

 

public static class Point{
	int r, c;
	public Point(int x, int y) {r = x; c = y;}
	public int hashCode() {return r*31+c; }
}
private static final int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
public static int findPerimeter(int[][] mat, int r, int c) {
	int m = mat.length, n = mat[0].length;
	boolean[][] visited = new boolean[m][n];
	int cnt = 0;
	Queue<Point> q = new LinkedList<>();
	q.offer(new Point(r,c));
	while(!q.isEmpty()) {
		Point p = q.poll();
		if(visited[p.r][p.c]) continue;
		visited[p.r][p.c] = true;
		boolean isEdge = false;
		for(int[] dir: dirs) {
			int i = p.r+dir[0], j = p.c+dir[1];
			if(i<0||j<0||i>=m||j>=n||mat[p.r][p.c]!=mat[i][j]) {
				isEdge = true;
			} else {
				q.offer(new Point(i,j));
			}
		}
		if(isEdge) cnt++;
	}
	return cnt;
}
public static void main (String[] args) {
	int[][] mat = { {1,1,2,2,3,4,5},
					{1,1,1,1,1,4,5},
					{1,1,1,1,1,4,5},
					{1,1,2,2,3,4,5}};
	System.out.println(findPerimeter(mat, 2, 1));
}