class Solution {
    // 深度优先搜索：往一个方向遍历，走到头就回溯，再往另外一个方向遍历
    // 广度优先搜索：从一个位置开始，向他的相邻位置搜索，逐层进行，用队列实现，需要用一个boolean数组进行标记,避免重复


     // 岛屿数量这个题是深度优先搜索和广度优先搜索的基础题
     // 深度优先代码相对简单，遍历字符数组，过程碰到'1'就进行深搜，深搜的过程只要判断是否越界，元素是否为'1'，对相邻'1'进行深度优先 
    int[][] pos = {{1,0}, {-1,0},{0,1},{0,-1}};
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int num = 0;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if ( grid[i][j] == '1') {
                    dfs(grid,i,j);
                    num++;
                }
            }
        }
        return num;
    }
    public void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0') {
             return;
         }
        
        grid[row][col] = '0';
        dfs(grid, row + 1, col);
        dfs(grid, row - 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row, col - 1);
    }
        
    // public void dfs (char[][] grid, int row, int col) {
    //     if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0') {
    //         return;
    //     }
    //     grid[row][col] = '0';
    //     dfs(grid, row - 1, col);
    //     dfs(grid, row + 1, col);
    //     dfs(grid, row, col + 1);
    //     dfs(grid, row, col - 1);
    // }
    public void bfs(char[][] grid, int row, int col, boolean[][] visited) {
        grid[row][col] = '0';
        visited[row][col] = true;
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{row,col});
        while (!que.isEmpty()) {
            int[] cur = que.poll();
            int x = cur[0];
            int y = cur[1];
            for (int[] tmp : pos) {
                int curX = tmp[0] + x;
                int curY = tmp[1] + y;
                if (curX < 0 || curX >= grid.length || curY < 0 || curY >= grid[0].length || grid[curX][curY] == '0' || visited[curX][curY]) {
                    continue;
                }
                que.offer(new int[]{curX, curY});
                visited[curX][curY] = true;
            }
            
        }
    }
}