Skip to content

Instantly share code, notes, and snippets.

@deyindra
Created June 3, 2016 06:18
Show Gist options
  • Save deyindra/342004da3906d97d360e96bbec0c94ee to your computer and use it in GitHub Desktop.
Save deyindra/342004da3906d97d360e96bbec0c94ee to your computer and use it in GitHub Desktop.
Given MXN metrics find number of group of similar Object (cluster of Object) which satisfy a given function
private static <T> boolean isSafe(
final T array[][],
final int rowIndex,
final int colIndex,
final boolean visited[][],
final Predicate<T> predicate){
final int ROW = array.length;
final int COL = array[0].length;
return (rowIndex >= 0) && (rowIndex < ROW) &&
(colIndex >= 0) && (colIndex < COL) &&
(predicate.test(array[rowIndex][colIndex])
&& !visited[rowIndex][colIndex]);
}
private static <T> void DFS(final T array[][],
final int rowIndex,
final int colIndex,
final boolean visited[][],
Predicate<T> predicate){
int rowNbr[] = new int[] {-1, -1, -1, 0, 0, 1, 1, 1};
int colNbr[] = new int[] {-1, 0, 1, -1, 1, -1, 0, 1};
visited[rowIndex][colIndex] = true;
for (int k = 0; k < 8; ++k)
if (isSafe(array,
rowIndex + rowNbr[k],
colIndex + colNbr[k],
visited,
predicate) )
DFS(array, rowIndex + rowNbr[k], colIndex + colNbr[k], visited,predicate);
}
public static <T> int count(T[][] array, Predicate<T> predicate){
final int ROW = array.length;
final int COL = array[0].length;
final boolean[][] visited = new boolean[ROW][COL];
int count=0;
for (int i = 0; i < ROW; ++i){
for (int j = 0; j < COL; ++j){
if(predicate.test(array[i][j]) && !visited[i][j]){
DFS(array,i,j,visited,predicate);
count++;
}
}
}
return count;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment