岛屿数量

class Solution:
    def solve(self , grid ):
        # write code here
        if not grid:
            return 0
        
        def dfs(i, j):
            grid[i][j] = '0'
            for x, y in [(i-1,j), (i+1,j), (i, j-1), (i, j+1)]:
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    dfs(x, y)
        
        m, n = len(grid), len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    res += 1
                    dfs(i, j)
        return res

/**
 * 判断岛屿数量
 * @param grid char字符型二维数组 
 * @param gridRowLen int grid数组行数
 * @param gridColLen int* grid数组列数
 * @return int整型
 */
void dfs(char** grid, int gridRowLen, int* gridColLen, int i, int j)
{
    if (i < 0 || i >= gridRowLen
        || j < 0 || j >= gridColLen[i]
        || grid[i][j] != '1') {
        return;
    }
    grid[i][j] = '2';
    dfs(grid, gridRowLen, gridColLen, i - 1, j);
    dfs(grid, gridRowLen, gridColLen, i + 1, j);
    dfs(grid, gridRowLen, gridColLen, i, j - 1);
    dfs(grid, gridRowLen, gridColLen, i, j + 1);
}

int solve(char** grid, int gridRowLen, int* gridColLen ) {
    int res = 0;
    for (int i = 0; i < gridRowLen; i++) {
        for (int j = 0; j < gridColLen[i]; j++) {
            if (grid[i][j] == '1') {
                res++;
                dfs(grid, gridRowLen, gridColLen, i, j);
            }
        }
    }
    return res;
}

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // 时间复杂度O(NM)，空间复杂度O(NM)
        int res = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    spread(grid, i, j);
                }
            }
        }
        return res;
    }
    void spread(vector<vector<char>> &grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0')
            return;
        grid[i][j] = '0';
        spread(grid, i - 1, j);
        spread(grid, i + 1, j);
        spread(grid, i, j - 1);
        spread(grid, i, j + 1);
    }
};

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        // write code here
        int len1 = grid.length;
        int len2 = grid[0].length;
        int res = 0;
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j,len1,len2);
                }
            }
        }
        return res;
    }
    private static void dfs(char[][] grid,int i,int j,int len1,int len2){

        if( i >= len1 || j >= len2 || grid[i][j] == '0'){
            return ;
        }   
        grid[i][j] = '0';
        if( i > 0){
            dfs(grid,i-1,j,len1,len2);
        }
        if( j > 0){
            dfs(grid,i,j-1,len1,len2);
        }
        dfs(grid,i+1,j,len1,len2);
        dfs(grid,i,j+1,len1,len2);
        
    }
}

提供一个不需要用到栈或者队列，又容易理解的思路：遍历矩阵，遇到‘1’就使岛屿数量+1.然后把这个点变为‘0’，并且使用递归把相邻的坐标也变成‘0’。需要注意的是，在使用递归的时候，要保证下标不超过边界。

import java.util.*;
public class Solution {
    public int solve (char[][] grid) {
         int islandcount=0;
         for(int i=0;i<grid.length;++i){
             for(int j=0;j<grid[0].length;++j){
                 if(grid[i][j]=='1'){
                     islandcount++;
                     clearpoint(i,j,grid);
                 }
             }
         }
        return islandcount;
    }
    void clearpoint(int i,int j,char[][]grid){
        if(i=grid.length||j=grid[0].length)return;
        if(grid[i][j]=='1'){
             grid[i][j]='0';
             clearpoint(i-1,j,grid);//上
             clearpoint(i+1,j,grid);//下
             clearpoint(i,j+1,grid);//右
             clearpoint(i,j-1,grid);//左
        }

    }
}

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */

    public int solve (char[][] grid) {
        // 岛屿数量
        int nums = 0;   
        // 0 没走过；1 走过
        byte[][] flag = new byte[grid.length][grid[0].length];
        LinkedList<Point> points = new LinkedList<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                // 找到一个没走过的岛屿起始点
                if(grid[i][j] == '1' && flag[i][j] == 0) {
                    points.add(new Point(i, j));
                    flag[i][j] = 1;
                    nums++;
                    while(!points.isEmpty()) {
                        Point t = points.pollFirst();
                        int x = t.x;
                        int y = t.y;
                        // 四周的点加入队列
                        if(x - 1 >= 0 && x - 1 < grid.length && grid[x - 1][y] == '1' && flag[x - 1][y] == 0) {
                            flag[x - 1][y] = 1;
                            points.add(new Point(x - 1, y));
                        }
                        if(x + 1 >= 0 && x + 1 < grid.length && grid[x + 1][y] == '1' && flag[x + 1][y] == 0) {
                            flag[x + 1][y] = 1;
                            points.add(new Point(x + 1, y));
                        }
                        if(y - 1 >= 0 && y - 1 < grid[0].length && grid[x][y - 1] == '1' && flag[x][y - 1] == 0) {
                            flag[x][y - 1] = 1;
                            points.add(new Point(x, y - 1));
                        }
                        if(y + 1 >= 0 && y + 1 <grid[0].length && grid[x][y + 1] == '1' && flag[x][y + 1] == 0) {
                            flag[x][y + 1] = 1;
                            points.add(new Point(x, y + 1));
                        }
                    }
                }
            }
        }
        return nums;
    }
}

import java.util.*;


public class Solution {
    
    public int solve (char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1') {
                    fun(grid, i, j);
                    count ++;
                }
            }
        }
        return count;
    }

    void fun(char[][] grid, int h, int w){
        if(grid[h][w] == '0') return;
        grid[h][w] = '0';
        if(h < grid.length - 1) fun(grid, h + 1, w);
        if(h > 0) fun(grid, h - 1, w);
        if(w < grid[0].length - 1) fun(grid, h, w + 1);
        if(w > 0) fun(grid, h, w - 1);
    }
}

public int solve (char[][] grid) {
        // 回溯  而不是dp
        //1是陆地 0是海洋
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){//注意这里是char 1,而不是int 1
                    build(grid,i,j);
                    ans++;//陆地数量+1
                }
            }
        }
        return ans;
    }
    public void build(char[][] grid,int i,int j){  //判断是不是陆地，不需要返回值
        int m=grid.length;
        int n=grid[0].length;
        //写截至条件
        //（这个对网格的控制要放在前面，先把有效范围卡死，再进行其他操作）
        if(i<0||j<0||i>=m||j>=n){//把i、j的取值分别控制在0~m-1或0~n-1
            return ;
        }
        if(grid[i][j]!='1'){//可能出现0（海水）、2（被沉没的陆地）
            return ;
        }
        //走到这里，说明当前网格是陆地1，沉没当前陆地变成2
        grid[i][j]='2';
        //回溯
        build(grid,i,j-1);
        build(grid,i,j+1);
        build(grid,i-1,j);
        build(grid,i+1,j);
    }

def find_block(grid, ind):
    i, j = ind
    grid[i][j] = 0
    if i - 1 >= 0:
        if grid[i - 1][j] == '1':
            grid[i - 1][j] = 0
            grid = find_block(grid, (i - 1, j))
    if i + 1 <= len(grid) - 1:
        if grid[i + 1][j] == '1':
            grid[i + 1][j] = 0
            grid = find_block(grid, (i + 1, j))
    if j - 1 >= 0:
        if grid[i][j - 1] == '1':
            grid[i][j - 1] = 0
            grid = find_block(grid, (i, j - 1))
    if j + 1 <= len(grid[0]) - 1:
        if grid[i][j + 1] == '1':
            grid[i][j + 1] = 0
            grid = find_block(grid, (i, j + 1))
    return grid


class Solution:
    def solve(self, grid) -> int:
        if len(grid) == 0:
            return 0
        num = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                ele = grid[i][j]
                if ele == '1':
                    grid = find_block(grid, (i, j))
                    num += 1
        return num

#include <array>
#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>>
     * @return int整型
     */
    struct location {//队列保存坐标
        int x, y;
        location(int i, int j): x(i), y(j) {}
    };
    void bfs(vector<vector<char>>& grid, int x, int y,
             vector<vector<char>>& visit) {
        location loc = location(x, y);
        queue<location> q;
        q.push(loc);
        int hangshu = grid.size(), lieshu = grid[0].size();
        while (!q.empty()) {
            location l = q.front();
            q.pop();
            int i = l.x, j = l.y;
            visit[i][j] = '1';
            if (i + 1 < hangshu && grid[i + 1][j] == '1' &&
                    visit[i + 1][j] == '0')q.push(location(i + 1, j));//right,满足条件入队
            if (i - 1 >= 0 && grid[i - 1][j] == '1' &&
                   visit[i - 1][j] == '0')q.push(location(i - 1, j));//left
            if (j + 1 < lieshu && grid[i][j + 1] == '1' &&
                    visit[i][j + 1] == '0')q.push(location(i, j + 1));//up
            if (j - 1 >= 0 && grid[i][j - 1] == '1' &&
                    visit[i][j - 1] == '0')q.push(location(i, j - 1));//down
        }
    }

    int solve(vector<vector<char> >& grid) {
        // write code here
        vector<vector<char>> visit = grid;
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    visit[i][j] = '0';//初始化visit
                } else visit[i][j] =
                        '1'; //1表示不可访问，包括已经访问的陆地和本就不可访问的海洋
            }
        }
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (visit[i][j] == '0' ) {
                    bfs(grid, i, j, visit);//满足条件直接进行一个广度遍历
                    count++;//+1岛
                }
            }
        }
        return count;
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
############ 求所有岛屿的面积，之后对面积列表求 len() ############# 
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        row = len(grid) 
        col = len(grid[0]) 
        
        if row == 0&nbs***bsp;col == 0 : 
            return 0 
        
        areasum = [] 
        for i in range(row): 
            for j in range(col): 
                res = 0
                que = [] 
                if grid[i][j] == "1": 
                    res += 1 
                    grid[i][j] = "0" 
                    que.append((i,j)) 
                    
                    while que: 
                        cur_i, cur_j = que.pop(0) 
                        
                        for x, y in [(0,1), (0,-1), (1,0), (-1,0)]: 
                            temp_i = cur_i + x 
                            temp_j = cur_j + y 
                            
                            if 0<=temp_i<row and 0<=temp_j<col and grid[temp_i][temp_j]=="1": 
                                res += 1 
                                grid[temp_i][temp_j] = "0" 
                                que.append((temp_i, temp_j))
                    areasum.append(res) ## 找出所有岛屿的面积和，然后求 len 
        print(areasum) 
        return len(areasum) 
###############################
################ 采用计数操作，计算岛屿面积 #################### 
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        row = len(grid) 
        col = len(grid[0]) 
        
        if row == 0&nbs***bsp;col == 0 : 
            return 0
        que = [] 
        count = 0 
        for i in range(row): 
            for j in range(col): 
                
                if grid[i][j] == "1": 
                    grid[i][j] = "0" 
                    que.append((i,j))
                    
                    while que: 
                        cur_i, cur_j = que.pop(0) 
                        
                        for x, y in [(0,1), (0,-1), (1,0), (-1,0)]: 
                            temp_i = cur_i + x 
                            temp_j = cur_j + y 
                            
                            if 0<=temp_i<row and 0<=temp_j<col and grid[temp_i][temp_j] == "1": 
                                grid[temp_i][temp_j] = "0"  
                                que.append((temp_i, temp_j))
                    count += 1 
        return count 

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        // write code here
        int islands = 0; 
        for(int i = 0; i < grid.length; i++) {
            for(int  j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == '1') {
                    islands++;
                    infect(grid,i,j);
                }
            }
        }
        return islands;
    }
    public void infect(char[][] grid, int i, int j) {
        if(i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = 2;
        infect(grid,i-1,j);
        infect(grid,i,j+1);
        infect(grid,i+1,j);
        infect(grid,i,j-1);
    }
}

遍历每个格子，寻找孤立的岛屿，如若找到则将该岛屿炸沉（将1变成0），继续遍历格子寻找岛屿

class Solution:
    def dfs(self, grid, i, j):
        n = len(grid)
        m = len(grid[0])
        grid[i][j] = '0'
        if i - 1 >= 0 and grid[i-1][j] == '1':
            self.dfs(grid, i-1, j)
        if i + 1 < n and grid[i+1][j] == '1':
            self.dfs(grid, i+1, j)
        if j - 1 >= 0 and grid[i][j-1] == '1':
            self.dfs(grid, i, j-1)
        if j + 1 < m and grid[i][j+1] == '1':
            self.dfs(grid, i, j+1)

    def solve(self , grid: List[List[str]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        count = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j)
        return count

import java.util.*;

//dfs
public class Solution {
    public int solve (char[][] grid) {
        int res = 0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j]=='1'){
                    dfs(i, j, grid);
                    res++;
                }
            }
        }
        return res;
    }
    
    private void dfs(int i, int j, char[][] grid){
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j]=='0') return;
        
        grid[i][j]='0';
        dfs(i+1, j, grid);
        dfs(i-1, j, grid);
        dfs(i, j-1, grid);
        dfs(i, j+1, grid);
    }
}