岛屿个数c++

参考文章

1. 岛屿个数1
2. 岛屿个数2

题目

输入样例：

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

输出样例：

1
3

样例解释

对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：

01111
11001
10201
10001
11111

岛屿 22 在岛屿 11 的 “环” 内部，所以岛屿 22 是岛屿 11 的子岛屿，答案为 11。

对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：

111111
100001
020301
100001
111111

注意岛屿 33 并不是岛屿 11 或者岛屿 22 的子岛屿，因为岛屿 11 和岛屿 22 中均没有“环”。

思路

遍历二维数组，遇到一块陆地‘1’，那么就把包含这块陆地的岛屿用bfs_islands函数搜索一遍，并标记这些块已经被搜索过了。然后，“派一些船”从该岛屿上一块陆地的八个方向出发，让船在海水上行驶，如果有船能到达“世界边缘”，那么说明该岛屿没有被包围。

最外层加一圈海水，这一圈海水即为世界边缘。

如果还是不太理解可以照着代码模拟一遍过程，就可以知道是如何得出答案的了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
//上右下左 左上 右上 右下 左下
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

char a[N][N];
int n, m;
//st_il[][]判断某快陆地是否被遍历过；st_sw[][]判断某片海水是否被遍历过
bool st_il[N][N], st_sw[N][N];

bool bfs_out(int x, int y)
{
  memset(st_sw, 0, sizeof(st_sw));//每次航海都要重置海水为：都没被遍历过
  
  queue<PII> q;
  q.push({x, y});
  st_sw[x][y] = true;
  
  while (q.size())
  {
    int t1 = q.front().first, t2 = q.front().second;
    q.pop();
    
    if(t1 <= 1 || t1 >= m || t2 <= 1 || t2 >= n)
    return true;
    
    for (int i = 0; i < 8; i ++)
    {
      int tx = t1 + dx[i], ty = t2 + dy[i];
      if (tx >= 0 && tx <= m + 1 && t2 >= 0 && t2 <= n + 1 && !st_sw[tx][ty] && a[tx][ty] == '0')
      {
        st_sw[tx][ty] = true;
        q.push({tx, ty});
      }
    }
  }
  return false;
}

void bfs_islands(int x, int y)
{
  queue<PII> q;
  q.push({x, y});
  st_il[x][y] = true;
  
  while (q.size())
  {
    int t1 = q.front().first, t2 = q.front().second;
    q.pop();
    
    for (int i = 0; i < 4; i ++)
    {
      int tx = t1 + dx[i], ty = t2 + dy[i];
      if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && !st_il[tx][ty] && a[tx][ty] == '1')
      {
        st_il[tx][ty] = true;
        q.push({tx, ty});
      }
    }
  }
}

void solve()
{
  
  cin >> m >> n;
  
  for (int i = 1; i <= m; i ++)
    for (int j = 1; j <= n; j ++)
      cin >> a[i][j];
      
  
  int res = 0;    
  for (int i = 1; i <= m; i ++)
    for (int j = 1; j <= n; j ++)
    {
      if (!st_il[i][j] && a[i][j] == '1')
      {
        bfs_islands(i, j);
        if (bfs_out(i, j)) res ++;
      }
    }
    
    cout << res << endl;
    memset(st_il, 0, sizeof(st_il));
}

int main()
{
  int T;
  cin >> T;
  
  while (T --)
  {
    solve();
  }
  return 0;
}