[java/4ms] DFS without extra space


  • 0
    public int numIslands(char[][] grid) {
            int cnt = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        islands(grid, i, j);
                        ++cnt;
                    }
                    // restore
                    if (grid[i][j] == '2')
                        grid[i][j] = '1';
                }
            }
            return cnt;
        }
        
        public void islands(char[][] chart, int i, int j) {
            if (chart[i][j] == '1') {
                chart[i][j] = '2';
                if (i - 1 >= 0)
                    islands(chart, i - 1, j);
                if (i + 1 < chart.length)
                    islands(chart, i + 1, j);
                if (j - 1 >= 0)
                    islands(chart, i, j - 1);
                if (j + 1 < chart[0].length)
                    islands(chart, i, j + 1);
            } 
        }
    

Log in to reply
 

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