Java BFS solution


  • 0
    K
    class Solution {
        private int numRow;
        private int numCol;
        private HashSet<String> set;
        class Point {
            int x;
            int y;
            Point (int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
        
        public int numDistinctIslands(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int max = 0;
            numRow = grid.length;
            numCol = grid[0].length;
            set = new HashSet<>();
            boolean[][] visited = new boolean[numRow][numCol];
            for (int i = 0; i < numRow; i++) {
                for (int j = 0; j < numCol; j++) {
                    if (!visited[i][j]) {
                        visited[i][j] = true;
                        if (grid[i][j] == 1) {
                            max = Math.max(max, visit(grid, visited, i, j));
                        }
                    }
                }
            }
            return set.size();
        }
        
        private int visit(int[][] grid, boolean[][] visited, int row, int col) {
            int[] rowMove = {1, -1, 0, 0};
            int[] colMove = {0, 0, 1, -1};
            Point curr = new Point(row, col);
            Queue<Point> queue = new LinkedList<>();
            int count = 0;
            queue.offer(curr);
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                curr = queue.poll();
                count++;
                for (int i = 0; i < rowMove.length; i++) {
                    int x = curr.x + rowMove[i];
                    int y = curr.y + colMove[i];
                    if (isValid(x, y) && !visited[x][y] && grid[x][y] == 1) {
                        sb.append((x - row) * 2 * numCol + (y - col));
                        sb.append(",");
                        visited[x][y] = true;
                        queue.offer(new Point(x, y));
                    }
                }
            }
            set.add(sb.toString());
            return count;
        }
        
        private boolean isValid(int row, int col) {
            return row >= 0 && col >= 0 && row < numRow && col < numCol;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.