Java BFS Solution


  • 0
    Y

    class Solution {

        public int numDistinctIslands(int[][] grid) {
            if (grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            List<Island> list = new ArrayList<>();
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] != 1) {
                        continue;
                    }
                    Island il = bfs(grid, i, j);
                    if (valid(il, list)) {
                        list.add(il);
                    }
                }
            }
            return list.size();
        }
        
        private Island bfs(int[][] grid, int m, int n) {
            int area = 0;
            List<Coordination> list = new ArrayList<>();
            
            int[] dx = {1, 0, -1, 0};
            int[] dy = {0, 1, 0, -1};
            Queue<Coordination> queue = new LinkedList<>();
            
            queue.offer(new Coordination(m, n));
            grid[m][n] = 2;
            
            while (queue.size() != 0) {
                Coordination coor = queue.poll();
                int y = coor.y;
                int x = coor.x;
                for (int i = 0; i < 4; i++) {
                    if (x + dx[i] < 0 || x + dx[i] == grid[0].length) {
                        continue;
                    }
                    if (y + dy[i] < 0 || y + dy[i] == grid.length) {
                        continue;
                    }
                    if (grid[y + dy[i]][x + dx[i]] != 1) {
                        continue;
                    }
                    queue.offer(new Coordination(y + dy[i], x + dx[i]));
                    list.add(new Coordination(y + dy[i] - m, x + dx[i] - n));
                    grid[y + dy[i]][x + dx[i]] = 2;
                }
                area++;
            }
            return new Island(area, list);
        }
        
        private boolean valid(Island il, List<Island> list) {
            for (Island island : list) {
                if (island.area != il.area) {
                    continue;
                }
                int count = 0;
                for (int i = 0; i < il.dir.size(); i++) {
                    Coordination a = il.dir.get(i);
                    Coordination b = island.dir.get(i);
                    if (a.y != b.y || a.x != b.x) {
                        break;
                    }
                    count++;
                }
                if (count == il.dir.size()) {
                    return false;
                }
            }
            return true;
        }
    }
    
    class Coordination {
        public int y;
        public int x;
        public Coordination(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    
    class Island {
        public int area;
        public List<Coordination> dir;
        public Island(int area, List<Coordination> dir) {
            this.area = area;
            this.dir = dir;
        }
    

    }


Log in to reply
 

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