飞地的数量问题
飞地的数量的题目
在m*n大小的gird里,其中0代表海洋,1代表陆地,题目为寻找被海洋包裹的陆地数目,最后返回值被海洋包围的陆地个数。
解题思路
首先飞地问题就是简单的矩阵遍历问题,在基本的矩阵遍历的基础上加上了一点点方法,就实现了飞地问题的解决。
首先我们先创建一个方法,DFS方法(深度优先搜索方法)
-
void DFS(int** grid,int i,int j,int n,int* m){
-
if(i<0||j<0||j=>m||i=>n) return;
-
if(grid[i][j]==0) return;
-
grid[i][j]=0;
-
DFS(grid,i,j 1,n,m);
-
DFS(grid,i,j-1,n,m);
-
DFS(grid,i 1,j,n,m);
-
DFS(grid,i-1,j,n,m);
-
}
这里也运用了递归的思想将在第i 1行,第j 1列的元素上下左右的结点进行检验,如果是陆地就将其改变为海洋,因为在C语言中不能运用grid.length,grid[0].length。所以在这个函数最后加上了整个矩阵的长度与宽度。(如果有大佬找到如何将矩阵的长宽带入该方法中希望在评论区留下您的足迹,小白真的很需要你的帮助)
其次我们先确定在矩阵边界的都不算,那么我们就先将在边界周围的陆地排除完,排除方法就是调用上述方法寻找靠近边界的陆地,并将它们改为海洋(为了方便在之后的长宽表示均用n,m)
-
for(int i=0;i<n;i ){
-
DFS(grid,i,0,n,m);
-
DFS(grid,i,m-1,n,m);
-
}
-
for(int j=0;j<m;j ){
-
DFS(grid,0,j,n,m);
-
DFS(grid,n-1,j,n,m);
-
}
最后我们直接将矩阵进行遍历遇见1的结点,用一个参数计数。(如果是检查岛屿数的话可以在)
-
for(int i=0;i<n;i )
-
for(int j=0;j<m;j ){
-
if(grid[i][j]==1) sum ;
-
}
-
for(int i=0;i<n;i )
-
for(int j=0;j<m;j ){
-
if(grid[i][j]==1){
-
sum ;
-
DFS(grid,i,j,n,m); //如果查询岛屿数就添加这个
-
}
-
}
在最后加上返回值就完成了。(下面有完整代码)
完整代码
-
void Dfs(int** grid,int i,int j,int n,int* m){
-
if(i<0||j<0||i>=n||j>=*m) return;
-
if(grid[i][j]==0) return;
-
grid[i][j]=0;
-
Dfs(grid,i,j 1,n,m);
-
Dfs(grid,i,j-1,n,m);
-
Dfs(grid,i 1,j,n,m);
-
Dfs(grid,i-1,j,n,m);
-
}
-
int numEnclaves(int** grid, int n, int* m){
-
int sum=0;
-
for(int i=0;i<n;i ){
-
Dfs(grid,i,0,n,m);
-
Dfs(grid,i,*m-1,n,m);
-
}
-
for(int j=0;j<*m;j ){
-
Dfs(grid,0,j,n,m);
-
Dfs(grid,n-1,j,n,m);
-
}
-
for(int i=0;i<=m-1;i )
-
for(int j=0;j<*m;j ){
-
if(grid[i][j]==1){
-
sum ;
-
}
-
}
-
return sum;
-
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfcjgk
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01