首页 > 试题广场 >

岛屿数量

[编程题]岛屿数量
  • 热度指数:109704 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。
例如:
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3
(注:存储的01数据其实是字符'0','1')
示例1

输入

[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]

输出

3
示例2

输入

[[0]]

输出

0
示例3

输入

[[1,1],[1,1]]

输出

1

备注:
01矩阵范围<=200*200
对于每个1,向四周扩充,无法继续扩充时该岛屿结束。扩充过程中处理过的格子后续直接跳过。

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        
        bool traversed[200][200]={0};
        
        int count=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(traversed[i][j]) continue;
                traversed[i][j] = true;
                if(grid[i][j]=='1')
                {
                    vector<int> activeSet;
                    activeSet.push_back(i*n+j);
                    while(!activeSet.empty())
                    {
                        vector<int> activeSetNew;
                        for(int idx:activeSet)
                        {
                            int row = idx/n;
                            int col = idx%n;
                            
                            if(row>0 && !traversed[row-1][col] && grid[row-1][col]=='1')
                                activeSetNew.push_back((row-1)*n+col);
                            if(row>0) traversed[row-1][col] = true;
                            
                            if(row<m-1 && !traversed[row+1][col] && grid[row+1][col]=='1')
                                activeSetNew.push_back((row+1)*n+col);
                            if(row<m-1) traversed[row+1][col] = true;
                            
                            if(col>0 && !traversed[row][col-1] && grid[row][col-1]=='1')
                                activeSetNew.push_back(row*n+col-1);
                            if(col>0) traversed[row][col-1] = true;
                            
                            if(col<n-1 && !traversed[row][col+1] && grid[row][col+1]=='1')
                                activeSetNew.push_back(row*n+col+1);
                            if(col<n-1) traversed[row][col+1] = true;
                        }
                        activeSet = activeSetNew;
                    }
                    count ++;
                }
            }
        }
        return count;
    }
};
发表于 2020-11-11 23:04:59 回复(0)

并查集和BFS

  • 算法
    • 并查集
    • 1.初始化并查集,用records[i*col+j]表示grid[i][j]节点
    • 2.count计数矩阵中1的个数,表示图的总分支
    • 3.遍历矩阵,当矩阵是1时,合并它右边和下边的1,合并成功分支减一,合并失败说明两个节点已经在同一个分支不再减一
    • 4.count表示图的分支即是岛屿的数量
    class UnionFind {
        private int[] records;
        public UnionFind(int n) {
            records = new int[n];
            for (int i = 0; i < n; i++) {
                records[i] = i;
            }
        }
        public int find(int x) {
            int fx = x;
            while (records[fx] != fx) {
                fx = records[fx];
            }
            // 压缩算法,简化时间
            while (x != fx) {
                int temp = records[x];
                records[x] = fx;
                x = temp;
            }
            return fx;
        }
        // true表示合并成功,false表示合并失败
        public boolean union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                records[fx] = fy;
                return true;
            }
            return false;
        }
    }
    public int solve (char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        UnionFind unionFind = new UnionFind(row*col);
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    if (i + 1 < row && grid[i+1][j] == '1' && unionFind.union(i * col + j, (i + 1) * col + j)) {
                        count--;
                    }
                    if (j + 1 < col && grid[i][j+1] == '1' && unionFind.union(i * col + j, i * col + (j + 1))) {
                        count--;
                    }
                }
            }
        }
        return count;
    }
  • 算法
    • bfs
    • 1.队列保存矩阵中1的坐标,通过bfs搜索附近四周同属一个岛屿的所有坐标,并置为0防止后续搜索重复计算
    • 2.搜索一次发现一座岛屿计数加一
    • 3.返回结果
    public int numIslands(char[][] grid) {
        // grid[x] == null; grid[x].length == 0; grid[x].length != grid[y].length;
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    Queue queue = new LinkedList();
                    queue.offer(new Point(i, j));
                    grid[i][j] = '0';
                    bfs(queue, grid);
                    count++;
                }
            }
        }
        return count;
    }
    public void bfs(Queue queue, char[][] grid) {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x = point.x;
            int y = point.y;
            if (x - 1 >= 0 && grid[x-1][y] == '1') {
                queue.offer(new Point(x-1, y));
                grid[x-1][y] = '0';
            }
            if (y - 1 >= 0 && grid[x][y-1] == '1') {
                queue.offer(new Point(x, y-1));
                grid[x][y-1] = '0';
            }
            if (x + 1 < grid.length && grid[x+1][y] == '1') {
                queue.offer(new Point(x+1, y));
                grid[x+1][y] = '0';
            }
            if (y + 1 < grid[0].length && grid[x][y+1] == '1') {
                queue.offer(new Point(x, y+1));
                grid[x][y+1] = '0';
            }
        }
    }
    class Point {
        int x;
        int y;
        Point (int _x, int _y) {
            x = _x;
            y = _y;
        }
    }
编辑于 2020-10-06 16:18:23 回复(1)
使用dfs,搜索时修改1为0。
class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    void dfs(vector<vector<char>> &grid, int i, int j){
        grid[i][j] = '0';
        if(i-1 >= 0 && grid[i-1][j] == '1')
            dfs(grid, i-1, j);
        if(i+1 < grid.size() && grid[i+1][j] == '1' )
            dfs(grid, i+1, j);
        if(j-1 >= 0 && grid[i][j-1] == '1')
            dfs(grid, i, j-1);
        if(j+1 < grid[0].size() && grid[i][j+1] == '1')
            dfs(grid, i, j+1);
    }
    int solve(vector<vector<char> >& grid) {
        // write code here
        int lands = 0;
        int N = grid.size();
        int M = grid[0].size();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(grid[i][j] == '1'){
                    lands++;
                    dfs(grid, i, j);
                }
            }
        }
        return lands;
    }
};


发表于 2020-08-30 00:56:13 回复(0)
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

发表于 2021-03-21 03:03:23 回复(0)
吐槽一下,01居然是字符不是数字,找了半天以为是代码逻辑的问题,差点怀疑人生~🤣
发表于 2021-03-21 13:58:15 回复(2)
解题思路:DFS
import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    int num=0;
    public int solve (char[][] grid) {
        // write code here
        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;
    }
    private void dfs(char[][] grid,int x,int y){
        if(x<0||y<0||x>grid.length-1||y>grid[0].length-1||grid[x][y]=='2'||grid[x][y]=='0') return;
        grid[x][y]='2';
        if(x>0&&grid[x-1][y]=='1')
            dfs(grid,x-1,y);
        if(x+1<grid.length&&grid[x+1][y]=='1')
            dfs(grid,x+1,y);
        if(y>0&&grid[x][y-1]=='1')
            dfs(grid,x,y-1);
        if(y+1<grid[0].length&&grid[x][y+1]=='1')
            dfs(grid,x,y+1);
        
    }
}


编辑于 2021-04-14 09:16:25 回复(0)
/**
 * 判断岛屿数量
 * @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;
}

发表于 2021-02-21 15:50:59 回复(1)
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);
    }
};

发表于 2022-10-14 23:58:59 回复(0)
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);
        
    }
}

发表于 2022-05-10 20:39:54 回复(0)
dfs填海
func solve( grid [][]byte ) (sum int) {
    row, col, sum := len(grid), len(grid[0]), 0
    var dfs func(int, int)
    dfs = func(x, y int) {
        if x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == '0' {
            return
        }
        grid[x][y]= '0'
        dfs(x+1, y)
        dfs(x, y+1)
        dfs(x-1, y)
        dfs(x, y-1)
    }
    for x:=0; x<row; x++ {
        for y:=0; y<col; y++ {
            if grid[x][y] == '1' {
                dfs(x, y)
                sum++
            }
        }
    }
    return
}


发表于 2021-11-23 16:30:23 回复(0)

提供一个不需要用到栈或者队列,又容易理解的思路:遍历矩阵,遇到‘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);//左
        }

    }
}
发表于 2021-10-08 09:50:18 回复(1)
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;
    }
}
发表于 2020-09-02 20:04:04 回复(1)
为什么只能过93.75%
function solve( grid ) {
    // write code here
    //使用dfs  回溯
    if(grid == null || grid.length == 0) return 0
    let num=0;
    let m = grid.length;
    let n = grid[0].length;
    let count = (i,j)=> {
        grid[i][j] = 0;//标记访问过
        if(i+1<m && grid[i+1][j]==1) count(i+1,j);
        if(i-1>=0 && grid[i-1][j]==1) count(i-1,j);
        if(j+1<n && grid[i][j+1]==1) count(i,j+1);
        if(j-1>=0 && grid[i][j-1]==1) count(i,j-1);
    }
    for(let i=0; i<m; i++){
        for(let j=0; j<n ; j++) {
            if(grid[i][j] == 1){
                count(i,j);
                num++;
            }
        }
    }
    return num
}


发表于 2020-09-01 16:27:16 回复(8)
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        m,n= len(grid),len(grid[0])
        def island(grid,x,y):
            if x < 0&nbs***bsp;x >= m&nbs***bsp;y < 0&nbs***bsp;y >= n&nbs***bsp;grid[x][y] == '0':#先判断当前是否为0,如果是,直接return
                return
            grid[x][y] = '0'#如果当前是1,再改成0
                
            island(grid,x-1,y)#上下左右继续找,如果找得到下一个1,则当前改成0,如果找不到,当前1不会被改成0
            #这样能保证最后的1不会被改掉,岛屿数量=最后剩的1的数量
                
            island(grid,x+1,y)
                
            island(grid,x,y-1)
                
            island(grid,x,y+1)
        res = 0
        for x in range(m):
            for y in range(n):
                if grid[x][y] == '1':#找所有初始1
                    res+=1
                    island(grid,x,y)#第一次进递归一定是1,从这个1开始改0
        return res
注释是我的理解,不知道对不对,求大佬指正


发表于 2024-02-19 15:39:13 回复(0)
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);
    }

发表于 2023-07-15 11:29:52 回复(1)
#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;
    }
};

发表于 2023-02-25 17:49:46 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 判断岛屿数量
# @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 

发表于 2022-08-30 15:33:28 回复(0)
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);
    }
}
发表于 2022-08-04 10:38:49 回复(0)

遍历每个格子,寻找孤立的岛屿,如若找到则将该岛屿炸沉(将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
发表于 2022-05-19 21:28:35 回复(0)
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);
    }
}

发表于 2021-09-14 16:36:29 回复(0)