中级农民
- 积分
- 155
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-4-17
- 最后登录
- 1970-1-1
|
写了下代码
- public class IslandNumberWithDifferentShapes {
- public static void main(String[] args) {
- int[][] matrix = {{ 1,0,1,0},
- {0,1,0,0},
- {0,0,0,0},
- {1,0,1,0},
- {0,1,0,0}};
- System.out.println(getIslandNumberWithDifferentShapes(matrix));
-
- }
-
- public static int getIslandNumberWithDifferentShapes(int[][] matrix) {
- if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
- return 0;
- }
-
- boolean[][] visited = new boolean[matrix.length][matrix[0].length];
- Set<String> set = new HashSet<String>();
- for (int i = 0; i < matrix.length; i++) {
- for (int j = 0; j < matrix[0].length; j++) {
- if (!visited[i][j] && matrix[i][j] == 1) {
- List<Integer> path = new ArrayList<Integer>();
- helper(matrix, visited, i, j, path);
- String str = transferToKey(path);
- set.add(str);
- }
- }
- }
-
- return set.size();
- }
- private static String transferToKey(List<Integer> path) {
- StringBuilder sb = new StringBuilder();
- int diff = path.get(0) - 0;
- for (int i : path) {
- sb.append((i - diff) + "#");
- }
- return sb.toString();
- }
- private static void helper(int[][] matrix, boolean[][] visited, int x,
- int y, List<Integer> path) {
- if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y] || matrix[x][y] != 1) {
- return;
- }
- int n = matrix[0].length;
- int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
- int[] dy = {0, 0, 1, -1, 1, -1, 1, -1};
- visited[x][y] = true;
- path.add((x * n + y));
- for (int i = 0; i < dx.length; i++) {
- int nx = dx[i] + x;
- int ny = dy[i] + y;
- helper(matrix, visited, nx, ny, path);
- }
- }
- }
复制代码 |
|