My BFS Solution in Java


  • 1
    S
    public int numDistinctIslands(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Set<String> st = new HashSet<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(!visited[i][j] && grid[i][j] == 1) {
                    String str = bfs(grid, visited, i, j);
                    st.add(str);
                }
            }
        }
        return st.size();
    }
    int[][] moves = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private String bfs(int[][] grid, boolean[][] visited, int row, int col) {
        Queue<int[]> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        q.add(new int[]{row, col});
        visited[row][col] = true;
        while(!q.isEmpty()) {
            int[] curCoor = q.poll();
            for(int i = 0; i < moves.length; i++) {
                int[] move = moves[i];
                int x = curCoor[0] + move[0];
                int y = curCoor[1] + move[1];
                if(isLegal(grid, x, y) && grid[x][y] == 1 && !visited[x][y]) {
                    visited[x][y] = true;
                    q.add(new int[]{x, y});
                    sb.append(i);
                }
            }
            sb.append(',');
        }
        return sb.toString();
    }
    private boolean isLegal(int[][] grid, int row ,int col) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[row].length;
    }
    

Log in to reply
 

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