当前位置:网站首页>leetcode1020. 飞地的数量(中等)
leetcode1020. 飞地的数量(中等)
2022-07-06 06:55:00 【重you小垃】
思路:dfs/bfs模板题
跟 leetcode130.被围绕的区域(中等) 类似
https://blog.csdn.net/zhangjiaji111/article/details/123668205
class Solution {
public:
int flag[505][505] = {
0};
int xy[4][2] = {
0, 1, 0, -1, 1, 0, -1, 0};
void dfs(vector<vector<int>>& grid, int x, int y) {
int n = grid.size(), m = grid[0].size();
flag[x][y] = 1;
for (int i = 0; i < 4; ++i) {
int xx = x + xy[i][0];
int yy = y + xy[i][1];
if (xx < 0 || xx > n - 1 || yy < 0 || yy > m - 1) continue;
if (grid[xx][yy] && !flag[xx][yy]) dfs(grid, xx, yy);
}
}
int numEnclaves(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
for (int j = 0; j < m; ++j) {
if (grid[0][j] && !flag[0][j]) dfs(grid, 0, j);
if (grid[n - 1][j] && !flag[n - 1][j]) dfs(grid, n - 1, j);
}
for (int i = 1; i < n - 1; ++i) {
if (grid[i][0] && !flag[i][0]) dfs(grid, i, 0);
if (grid[i][m - 1] && !flag[i][m - 1]) dfs(grid, i, m - 1);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] && !flag[i][j]) ans++;
}
}
return ans;
}
};
思路三:并查集
具体思路:设置一个虚拟的陆地:n*m,初始化时边缘的陆地与该单元格连通。然后将图中的1构造若干个连通分量。
ans:单元格为1且与n*m的findfather()相等的个数。
class Solution {
public:
vector<int> father;
void unite (int u, int v) {
int fau = findfather(u);
int fav = findfather(v);
if (fau != fav) father[fau] = fav;
}
int findfather(int m) {
if (father[m] == m) return m;
return father[m] = findfather(father[m]);
}
int numEnclaves(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
father.resize(n * m + 1);
for (int i = 0; i < m * n + 1; ++i) {
father[i] = i;
}
auto getindex = [&](int x, int y) {
return x * m + y;
};
for (int j = 0; j < m; ++j) {
if (grid[0][j]) unite(getindex(0, j), n * m);
if (grid[n - 1][j]) unite(getindex(n - 1, j), n * m);
}
for (int i = 1; i < n - 1; ++i) {
if (grid[i][0]) unite(getindex(i, 0), n * m);
if (grid[i][m - 1]) unite(getindex(i, m - 1), n * m);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j]) {
if (i - 1 >= 0 && grid[i - 1][j]) unite(getindex(i - 1, j), getindex(i, j));
if (j - 1 >= 0 && grid[i][j - 1]) unite(getindex(i, j - 1), getindex(i, j));
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] && findfather(getindex(i, j)) != findfather(n * m)) ans++;
}
}
return ans;
}
};
边栏推荐
- Refer to how customer push e-commerce does content operation
- GET 和 POST 请求类型的区别
- Leetcode - 152 product maximum subarray
- Basic commands of MySQL
- [brush questions] how can we correctly meet the interview?
- Windows Server 2016 standard installing Oracle
- 编译,连接 -- 笔记 -2
- Fedora/rehl installation semanage
- 这个高颜值的开源第三方网易云音乐播放器你值得拥有
- 接口自动化测试框架:Pytest+Allure+Excel
猜你喜欢
Supporting title of the book from 0 to 1: ctfer's growth road (Zhou Geng)
ROS学习_基础
Development of entity developer database application
【服务器数据恢复】IBM服务器raid5两块硬盘离线数据恢复案例
女生学软件测试难不难 入门门槛低,学起来还是比较简单的
UWA Pipeline 2.2.1 版本更新说明
AI on the cloud makes earth science research easier
攻防世界 MISC中reverseMe简述
Entity Developer数据库应用程序的开发
Depth residual network
随机推荐
【服务器数据恢复】IBM服务器raid5两块硬盘离线数据恢复案例
Office doc add in - Online CS
Day 239/300 注册密码长度为8~14个字母数字以及标点符号至少包含2种校验
机器人类专业不同层次院校课程差异性简述-ROS1/ROS2-
Redis Foundation
Entity Developer数据库应用程序的开发
Day 248/300 关于毕业生如何找工作的思考
BUU的MISC(不定时更新)
Bio model realizes multi person chat
ML之shap:基于adult人口普查收入二分类预测数据集(预测年收入是否超过50k)利用Shap值对XGBoost模型实现可解释性案例之详细攻略
成功解决TypeError: data type ‘category‘ not understood
将ue4程序嵌入qt界面显示
Fast target recognition based on pytorch and fast RCNN
软件测试外包到底要不要去?三年真实外包感受告诉你
漏了监控:Zabbix对Eureka instance状态监控
ROS learning_ Basics
Reflex WMS medium level series 3: display shipped replaceable groups
[hot100] 739. Température quotidienne
Chapter 7 - thread pool of shared model
前缀和数组系列