给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
示例 2：
输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
标签：
['深度优先搜索', '广度优先搜索', '并查集', '数组', '矩阵']难度：Medium
喜欢：1830blablabla
class Solution {
int m, n;
int[] dr = {0, 1, 0, -1, 0};
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
m = grid.length;
n = grid[0].length;
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
cnt++;
floodFill(grid, i, j);
}
}
}
return cnt;
}
public void floodFill(char[][] grid, int x, int y) {
grid[x][y] = '0';
for (int d = 0; d < 4; d++) {
int dx = x + dr[d], dy = y + dr[d + 1];
if (dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == '1') {
floodFill(grid, dx, dy);
}
}
}
}class Solution {
public:
int d[5] = {-1, 0, 1, 0, -1};
int m, n;
void floodFill(vector<vector<char>> &g, int i, int j) {
g[i][j] = '0';
for (int u = 0; u < 4; u++) {
int x = i + d[u], y = j + d[u + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == '1'){
floodFill(g, x, y);
}
}
}
int numIslands(vector<vector<char>> &g) {
m = g.size();
n = g[0].size();
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '0')continue;
res++;
floodFill(g, i, j);
}
}
return res;
}
};class Solution {
int[] mv = {0, 1, 0, -1, 0};
int m, n;
void bfs(char[][] grid, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
while (!queue.isEmpty()) {
int k = queue.size();
while (k-- > 0) {
int[] top = queue.poll();
for (int d = 0; d < 4; d++) {
int dx = top[0] + mv[d], dy = top[1] + mv[d + 1];
if (dx >= 0 && dx < m && dy >=0 && dy < n) {
if (grid[dx][dy] == '1') {
grid[dx][dy] = '0';
queue.add(new int[]{dx, dy});
}
}
}
}
}
}
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
m = grid.length;
n = grid[0].length;
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
cnt++;
grid[i][j] = '0';
bfs(grid, i, j);
}
}
}
return cnt;
}
}class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
typedef pair<int, int> PII;
int m = grid.size(), n = grid[0].size();
queue<PII> q;
int cnt = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i< m ; i++){
for (int j =0; j < n; j++){
if (grid[i][j] == '1') {
cnt ++;
q.push({i, j});
grid[i][j] = '0';
while (!q.empty()){
auto f = q.front();
q.pop();
for (int d = 0; d < 4; d++){
int x = dx[d] + f.first, y = dy[d] + f.second;
if (x >=0 && x< m && y >=0 && y < n && grid[x][y] == '1'){
grid[x][y] = '0';
q.push({x, y});
}
}
}
}
}
}
return cnt;
}
};-
把一个岛屿的点合并成一个连通块
-
统计连通块 的数量
-
$K$ 为连通块的平均大小
class Solution {
public:
vector<int> f;
int dx[2] = { 0, 1}, dy[2] = { 1, 0};
int numIslands(vector <vector<char>> &grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size();
f = vector<int>(m * n);
for (int i = 0; i < f.size(); i++)f[i] = i;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
for (int d = 0; d < 2; d++){
int x = i + dx[d], y = j + dy[d];
if (x>=0 && x < m && y>=0 && y<n && grid[x][y] == '1'){
f[find(n * i + j)] = find(n * x + y);
}
}
}
}
}
int cnt = 0;
for (int i = 0; i < f.size(); i++) {
if (f[i] == i && grid[i/n][i%n] == '1') cnt++;
}
return cnt;
}
int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
};class Solution {
public:
int m, n;
static const int N = 100000;
int f[N];
int find(int x){
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
void uu(int x, int y){
int p = find(x), q = find(y);
if (p != q) {
f[p] = q;
}
}
int ch(int x, int y) {
return x * n + y;
}
int numIslands(vector<vector<char>>& g) {
m = g.size(), n = g[0].size();
for (int i = 0; i< m * n; i++) f[i] = i;
for (int i =0; i< m; i++){
for (int j =0; j< n; j++){
if (i+ 1< m && g[i][j]== '1' && g[i+1][j]== '1') {
uu(ch(i, j), ch(i+1, j));
}
if (j+1 <n && g[i][j]== '1' && g[i][j + 1]== '1') {
uu(ch(i, j), ch(i, j+1));
}
}
}
int cnt = 0;
for (int i = 0; i< m * n; i++) {
if (f[i] == i && g[i/n][i%n] == '1') cnt++;
}
return cnt;
}
};