LEETCODE算法:200. Number of Islands

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: 11110 11010 11000 00000

Output: 1 Example 2:

Input: 11000 11000 00100 00011

Output: 3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//广度优先遍历
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        int dirs[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
        queue<pair<int,int>> q;
        int ans=0;
        for(int t1=0;t1<grid.size();t1++){
            for(int t2=0;t2<grid[0].size();t2++)
            {
                if(grid[t1][t2]=='1')
                {
                    ans++;
                    q.push({t1,t2});
                } 
                while(!q.empty())
                {
                    auto [i,j]=q.front();
                    q.pop();
                    //grid[i][j]==0
                    for(int k=0;k<4;k++)
                    {
                        int ni=i+dirs[k][0];
                        int nj=j+dirs[k][1];
                        if(ni>=0&&nj>=0&&ni<grid.size()&&nj<grid[0].size()&&grid[ni][nj]=='1')
                        {
                            q.push({ni,nj});
                            grid[ni][nj]='0';
                        } 
                    }
                }
            }
        }

        return ans;
    }
};

说明

  • 使用原本数组取代了vis数组，节约内存
  • 不能把标记已经走过放到循环外(上面代码注释语句处)，否则会导致增加大量判断以至于超时
  • 深度优先搜索同样可以实现