第十四届省赛大学B组(C/C++)岛屿个数

简介: 第十四届省赛大学B组(C/C++)岛屿个数

题目链接:岛屿个数

小蓝得到了一副大小为 M×N 的格子地图,可以将其视作一个只包含字符 0(代表海水)和 1(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。

在岛屿 A 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列:(x0,y0),(x1,y1),...,(xk−1,yk−1),其中 (x(i+1)%k,y(i+1)%k) 是由 (xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1),此时这 k 个格子就构成了一个 “环”。

如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部,此时我们将岛屿 B 视作是岛屿 A 的子岛屿。

若 B 是 A 的子岛屿,C 又是 B 的子岛屿,那 C 也是 A 的子岛屿。

请问这个地图上共有多少个岛屿?

在进行统计时不需要统计子岛屿的数目。


输入格式:


第一行一个整数 T,表示有 T 组测试数据。


接下来输入 T 组数据。


对于每组数据,第一行包含两个用空格分隔的整数 M、N 表示地图大小;接下来输入 M行,每行包含 N 个字符,字符只可能是 0 或 1。


输出格式:


对于每组数据,输出一行,包含一个整数表示答案。


数据范围:


对于 30% 的评测用例,1≤M,N≤10。

对于 100% 的评测用例,1≤T≤10,1≤M,N≤50。


输入样例:

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

输出样例:

1
3

样例解释

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

01111
11001
10201
10001
11111

岛屿 2 在岛屿 1 的 “环” 内部,所以岛屿 2 是岛屿 1 的子岛屿,答案为 1。

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

111111
100001
020301
100001
111111

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿,因为岛屿 1 和岛屿 2 中均没有“环”。


解题思路:

这不是普通的DFS/BFS搜索题,看着很像最少连通块,但是题目中又有了新的定义就是在陆地环里面(被陆地包围)也算属于此外围岛屿,那么我们就也要判定这种环岛屿,博主的思路是先BFS也可DFS找出连通块的个数(四个方向),建一个vector把连通块的起点存进去,方便去找环岛屿,只要有一个起点(或者此连通块任意一个点),此连通块的点便可通过移动一网打尽,再BFS(或者DFS)判定该岛屿是否属于这种环岛屿,不属于就结果加一,属于就不用加。


那么如何判断是否输入环岛屿呢,我们观察样例中图,我们把图中外围再加上一圈称为“外海”,我们用vector存了每个连通块的起点,在这个起点上八个方向去DFS(或BFS),只要它达不到外海,说明它肯定被陆地所包围,也就是所说的环岛屿。图中外围都是0(海水),绿色框是每个连通块的起点,此起点只要能达到红色0(外海)就不是环岛屿。图中为2点,无论如何走都到达不了外海。

第二个样例三个起点(绿色框)都可以到达外海,注意判断环岛屿是八个方向,连通块个数是四个方向。


AC代码(BFS+DFS):

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int N = 55;
typedef pair<int, int> PII;
int T, n, m, res;
int a[N][N],b[N][N];//a为原数组,b为找环岛屿中介数组
char ch[N][N];//输入原数组
bool vis[N][N];//DFS标记数组
bool flag;//是否为环岛屿
vector<PII> v;
int dx[] = { 0,0,1,-1 };//dxdy为遍历岛屿个数
int dy[] = { 1,-1,0,0 };
int dx1[] = { 0,0,1,1,1,-1,-1,-1 };//dx1dy1为遍历岛屿是否为环岛屿
int dy1[] = { 1,-1,1,-1,0,1,-1,0 };
queue<PII> q;
void bfs() {//找岛屿个数
  while (q.size()) {
    auto t = q.front();
    q.pop();
    a[t.first][t.second] = 0;
    for (int i = 0; i < 4; i++) {
      int x = t.first + dx[i];
      int y = t.second + dy[i];
      if (x <= 0 || y <= 0 || x > m || y > n) {
        continue;
      }
      if (a[x][y] == 0) {
        continue;
      }
      a[x][y] = 0;//不用vis数组,直接自身标记
      q.push({ x,y });
    }
  }
}
void dfs(int x,int y) {//遍历海,是否为环岛屿
  if (x == 0 || x == m + 1 || y == 0 || y == n + 1) {
    flag = 1;//不是环岛屿
    return;
  }
  for (int i = 0; i < 8; i++) {
    int bx = x + dx1[i];
    int by = y + dy1[i];
    if (bx<0 || bx>m + 1 || by<0 || by>n + 1)continue;
    if (b[bx][by] == 1||vis[bx][by])continue;
    vis[bx][by] = 1;
    dfs(bx, by);
  }
}
int main() {
  cin >> T;
  while (T--) {
    cin >> m >> n;
    memset(a, 0, sizeof(a));//多组输入,注意初始化
    memset(b, 0, sizeof(b));
    v.clear();
    res = 0;
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        cin >> ch[i][j];
        a[i][j] = ch[i][j] - '0';
        b[i][j] = ch[i][j] - '0';//把原数组复制b一份,这样dfs便可以直接操作
      }
    }
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (a[i][j]) {//是陆地就BFS找此连通块都标记为海洋
          q.push({ i,j });
          v.push_back({ i,j });//记录起点,dfs找环岛屿用
          bfs();
        }
      }
    }
    for (auto i : v) {
      flag = false;//每一个起点都要初始化
      memset(vis, 0, sizeof(vis));
      dfs(i.first, i.second);
      if (flag==1) {//不是环岛屿
        res++;
      }
    }
    cout << res << endl;
  }
  return 0;
}

相关文章
|
7月前
|
C++ Java Go
C/C++每日一练(20230409) 岛屿数量、出现次数最多整数、两数相除
C/C++每日一练(20230409) 岛屿数量、出现次数最多整数、两数相除
50 0
C/C++每日一练(20230409) 岛屿数量、出现次数最多整数、两数相除
|
12天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
25 2
|
18天前
|
存储 编译器 C++
【c++】类和对象(下)(取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象)
本文介绍了C++中类和对象的高级特性,包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项,帮助读者深入了解C++面向对象编程的核心机制。
53 5
|
24天前
|
存储 编译器 C++
【c++】类和对象(中)(构造函数、析构函数、拷贝构造、赋值重载)
本文深入探讨了C++类的默认成员函数,包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化,析构函数用于对象销毁时的资源清理,拷贝构造函数用于对象的拷贝,赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项,并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
56 4
|
26天前
|
存储 编译器 Linux
【c++】类和对象(上)(类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针)
本文介绍了C++中的类和对象,包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用,以及如何使用访问限定符控制成员的访问权限。此外,还讨论了对象的内存分配规则和this指针的使用场景,帮助读者深入理解面向对象编程的核心概念。
57 4
|
2月前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象(下)
【C++打怪之路Lv5】-- 类和对象(下)
28 4
|
2月前
|
编译器 C语言 C++
【C++打怪之路Lv4】-- 类和对象(中)
【C++打怪之路Lv4】-- 类和对象(中)
25 4
|
2月前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
23 1
|
2月前
|
存储 编译器 C++
【C++类和对象(下)】——我与C++的不解之缘(五)
【C++类和对象(下)】——我与C++的不解之缘(五)
|
2月前
|
编译器 C++
【C++类和对象(中)】—— 我与C++的不解之缘(四)
【C++类和对象(中)】—— 我与C++的不解之缘(四)