Number of Distinct Islands
2018-06-27 本文已影响8人
Frank_Kivi
https://www.lintcode.com/problem/number-of-distinct-islands/description
import java.util.HashSet;
import java.util.Set;
public class Solution {
/**
* @param grid: a list of lists of integers
* @return: return an integer, denote the number of distinct islands
*/
public int numberofDistinctIslands(int[][] grid) {
// write your code here
Set<String> set = new HashSet<>();
for (int i = 0; i < grid.length; i++) {
int[] ints = grid[i];
for (int j = 0; j < ints.length; j++) {
int anInt = ints[j];
if (anInt == 1) {
StringBuilder stringBuilder = new StringBuilder();
treeWalk(i, j, i, j, stringBuilder, grid);
set.add(stringBuilder.toString());
}
}
}
return set.size();
}
private void treeWalk(int i, int j, int y, int x, StringBuilder stringBuilder, int[][] grid) {
if (i < grid.length && i >= 0 && j < grid[0].length && j >= 0 && grid[i][j] == 1) {
grid[i][j] = 0;
stringBuilder.append(y - i);
stringBuilder.append(x - j);
treeWalk(i + 1, j, y, x, stringBuilder, grid);
treeWalk(i - 1, j, y, x, stringBuilder, grid);
treeWalk(i, j + 1, y, x, stringBuilder, grid);
treeWalk(i, j - 1, y, x, stringBuilder, grid);
}
}
}