当前位置:网站首页>1254. 统计封闭岛屿的数目
1254. 统计封闭岛屿的数目
2022-06-30 11:41:00 【蓝莓侠】
这道题没做出来,看题解还看了半天,首先套圈的情况是不算两个的,而且四个1不算。
做法确实没想出来。什么叫封闭,是指到了边上还没有1。有了这句话就出来了。既然这样,就遍历所有的0,向0的上下左右遍历,如果到边上就认为不是封闭。同时遍历过的节点要标记一下,防止多次遍历,这里是学的题解还用1,要是我自己想肯定是2,避免重复。
#include<stdc++.h>
using namespace std;
bool is_island;
void dfs(vector<vector<int>>&grid, int x, int y)
{
if(x<0 || x>=(int)grid.size() || y<0 || y>=(int)grid[0].size())
{
is_island = false;
return;
}
if(grid[x][y]==0)
{
grid[x][y] = 1;
dfs(grid, x+1, y);
dfs(grid, x, y+1);
dfs(grid, x-1, y);
dfs(grid, x, y-1);
}
}
int closedIsland(vector<vector<int>>& grid) {
int count = 0;
for(int i=1; i<(int)grid.size()-1;i++)
{
for(int j=1; j<(int)grid[0].size()-1; j++)
{
if(grid[i][j]==0)
{
is_island = true;
dfs(grid, i,j);
if(is_island)
count++;
}
}
}
return count;
}
int main()
{
int x[5][8] = {
{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0,1},{1,1,1,1,1,1,1,0}};
vector<vector<int>> a;
for(int i=0; i<5;i++)
{
vector<int>b;
for(int j=0; j<8;j++)
{
b.push_back(x[i][j]);
}
a.push_back(b);
}
cout<<closedIsland(a)<<endl;
return 0;
}
边栏推荐
- In depth analysis of Apache bookkeeper series: Part 4 - back pressure
- AutoCAD - len command
- ClipboardJS——开发学习总结1
- 使用深度学习进行生物网络分析
- 治数如治水,数据治理和数据创新难在哪?
- 1175. 质数排列
- How to 'gracefully' avoid MySQL login prompt information in scripts
- Pointdistiller: structured knowledge distillation for efficient and compact 3D detection
- 这些电影中的科幻构想,已经用AI实现了
- Goto statement jump uninitialized variable: c2362
猜你喜欢
wallys/3×3 MIMO 802.11ac Mini PCIe Wi-Fi Module, QCA9880, 2,4GHz / 5GHzDesigned for Enterprise
聊聊怎么做硬件兼容性检测,快速迁移到openEuler?
There are so many kinds of coupons. First distinguish them clearly and then collect the wool!
Limited time appointment | Apache pulsar Chinese developer and user group meeting in June
Stm32f407zgt6 uses SDIO mode to drive SD card
Speech recognition - Fundamentals (I): introduction [speech to text]
一瓶水引发的“战争”
Dameng data rushes to the scientific innovation board, or becomes the "first share of domestic database" in the A-share market
“\“id\“ contains an invalid value“
这些电影中的科幻构想,已经用AI实现了
随机推荐
【云原生 | Kubernetes篇】深入了解Deployment(八)
HMS Core音频编辑服务3D音频技术,助力打造沉浸式听觉盛宴
他是上海两大产业的第一功臣,却在遗憾中默默离世
If it is not listed again, Kuangshi technology will not be able to endure
wallys/600VX – 2×2 MIMO 802.11ac Mini PCIe Wi-Fi Module, Dual Band, 2,4GHz / 5GHz QCA 9880
VScode选中多个单词
Quel est le rôle du rétroéclairage LED?
这些电影中的科幻构想,已经用AI实现了
数据库 自动增长
Limited time appointment | Apache pulsar Chinese developer and user group meeting in June
论文解读(AGC)《Attributed Graph Clustering via Adaptive Graph Convolution》
Le talent scientifique 丨 dessins animés qu'est - ce qu'erdma?
Redis - ziplist compressed list
Database connection pool Druid
Alibaba cloud database represented by polardb ranks first in the world
nvm安装node后,在使用npm指令时候显示不是内部或外部指令
60 divine vs Code plug-ins!!
Review the writing software with characteristics
60 个神级 VS Code 插件!!
数据库 事务