网站的规划与建设_按时间顺序可以分为哪等五个阶段,天津企业网站建设哪家好,惠东县网站建设,网站首页的功能目录 题目链接#xff1a;岛屿个数
解题思路#xff1a;
AC代码#xff08;BFSDFS#xff09;#xff1a; 题目链接#xff1a;岛屿个数
小蓝得到了一副大小为 MN 的格子地图#xff0c;可以将其视作一个只包含字符 0#xff08;代表海水#xff09;和 1#xff0…目录 题目链接岛屿个数
解题思路
AC代码BFSDFS 题目链接岛屿个数
小蓝得到了一副大小为 M×N 的格子地图可以将其视作一个只包含字符 0代表海水和 1代表陆地的二维数组地图之外可以视作全部是海水每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。
在岛屿 A 所占据的格子中如果可以从中选出 k 个不同的格子使得他们的坐标能够组成一个这样的排列(x0,y0),(x1,y1),...,(xk−1,yk−1)其中 (x(i1)%k,y(i1)%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≤101≤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代码BFSDFS
#includeiostream
#includequeue
#includecstring
#includevector
using namespace std;
const int N 55;
typedef pairint, 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;//是否为环岛屿
vectorPII 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 };
queuePII 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 (bx0 || bxm 1 || by0 || byn 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 (flag1) {//不是环岛屿res;}}cout res endl;}return 0;
}
