Skip to content

Instantly share code, notes, and snippets.

@shixiaoyu

shixiaoyu/NumberOfIslandsDFS.java

Created May 25, 2020 18:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shixiaoyu/1882de7f135cc86ce1677137efb57c31 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shixiaoyu/1882de7f135cc86ce1677137efb57c31 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. shixiaoyu created this gist May 25, 2020.
    34 changes: 34 additions & 0 deletions NumberOfIslandsDFS.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,34 @@
    private final int[] xDirection = {1, 0, -1, 0};
    private final int[] yDirection = {0, -1, 0, 1 };

    public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
    return 0;
    }

    int m = grid.length;
    int n = grid[0].length;
    int islandCount = 0;
    boolean[][] visited = new boolean[m][n];

    for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    if (grid[i][j] == '0' || visited[i][j]) {
    continue;
    }
    explore(i, j, m, n, grid, visited);
    islandCount++;
    }
    }

    return islandCount;
    }

    private void explore(int x, int y, int row, int col, char[][] grid, boolean[][] visited) {
    if (!this.shouldExplore(x, y, row, col, grid, visited)) return;

    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
    explore(x + this.xDirection[i], y + this.yDirection[i], row, col, grid, visited);
    }
    }