200. 岛屿数量

难度中等515

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

1
2
3
4
5
6
输入:
11110
11010
11000
00000
输出: 1

示例 2:

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解法1:BFS 遍历每一个点,遇到1就bfs并且把bfs到的1变成0;记录bfs的次数即可：

测试数据竟然有空集，这样会导致int maxn=map[0].size();//列数; 出现runtime error神必报错我tm……

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        //感觉可以bfs
        //遍历map的每一个点,如果map[i][j]是1,进行bfs,遇到1的变成0;
        vector<vector<char>>map(grid);
        int cnt=0;
        //m*n;
        
        int maxm=map.size();//行数
        if(maxm==0){return 0;}//对付空集的神必特判
        int maxn=map[0].size();//列数;
        
        for(int i=0;i<maxm;i++){
            for(int j=0;j<maxn;j++){
                if(map[i][j]=='1'){
                    cnt+=1;
                    queue<pair<int,int>>q;
                    pair<int,int>temp;
                    temp.first=i;
                    temp.second=j;
                    q.push(temp);
                    map[i][j]='0';
                    while(!q.empty()){
                        pair<int,int>cur=q.front();
                        q.pop();
                        int tempi=cur.first;
                        int tempj=cur.second;
                        if(tempi-1>=0&&map[tempi-1][tempj]=='1'){
                            pair<int,int>temp2;
                            temp2.first=tempi-1;
                            temp2.second=tempj;
                            q.push(temp2);
                            map[tempi-1][tempj]='0';
                        }
                        if(tempi+1<maxm&&map[tempi+1][tempj]=='1'){
                            pair<int,int>temp2;
                            temp2.first=tempi+1;
                            temp2.second=tempj;
                            q.push(temp2);
                            map[tempi+1][tempj]='0';
                        }
                        if(tempj-1>=0&&map[tempi][tempj-1]=='1'){
                            pair<int,int>temp2;
                            temp2.first=tempi;
                            temp2.second=tempj-1;
                            q.push(temp2);
                            map[tempi][tempj-1]='0';
                        }
                        if(tempj+1<maxn&&map[tempi][tempj+1]=='1'){
                            pair<int,int>temp2;
                            temp2.first=tempi;
                            temp2.second=tempj+1;
                            q.push(temp2);
                            map[tempi][tempj+1]='0';
                        }
                        ;
                    }
                    
                    ;
                }
            }
        }


        return cnt;
    }
};