当前位置:网站首页>Combined search /dfs solution - leetcode daily question - number of 1020 enclaves
Combined search /dfs solution - leetcode daily question - number of 1020 enclaves
2022-07-06 09:46:00 【C+++++++++++++++++++】
List of articles
Title Description
title
One 、 Take the boundary value as the object to search and solve
At the beginning, I soon thought of using more violent direct dfs Deep search , And then it's over time .
Pay attention to this question because 1
Whether it can be extended to the whole border is valid by judging from outside 1
So we need to be clever , It should be based on all boundaries 1
For the object, first put all that can be exceeded 1
I found out , Then the rest 1
That's the answer .
Two 、 And look up the set and merge + Whether the border attribute is updated
Create a query set , Use a one-dimensional array to store all the elements of a two-dimensional array , At the same time, a one-dimensional array is added to determine whether the boundary is contiguous , Every time merge During the operation, it is necessary to judge whether the merge operation and the border update should be performed at the same time .
First use and search set merge be-all 1
, Then judge whether it is contiguous one by one .
Solution code
dfs Method :
class Solution {
public:
vector<vector<int>> dirs = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}};
int numEnclaves(vector<vector<int>>& grid) {
this->m = grid.size();
this->n = grid[0].size();
this->visited = vector<vector<bool>>(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
for (int j = 1; j < n - 1; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
int enclaves = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
enclaves++;
}
}
}
return enclaves;
}
void dfs(const vector<vector<int>> & grid, int row, int col) {
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
return;
}
visited[row][col] = true;
for (auto & dir : dirs) {
dfs(grid, row + dir[0], col + dir[1]);
}
}
private:
int m, n;
vector<vector<bool>> visited;
};
And look up the collection method :
// This parallel search set is well written
class UnionFind {
public:
UnionFind(const vector<vector<int>> & grid) {
int m = grid.size(), n = grid[0].size();
this->parent = vector<int>(m * n); // The connection relationship between storage and collection
this->onEdge = vector<bool>(m * n, false);// The key to finding whether there is a boundary element
this->rank = vector<int>(m * n);
for (int i = 0; i < m; i++) {
// Update and search the set according to the transmitted two-dimensional array , Simultaneous updating onEdge The boundary element is true
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int index = i * n + j;
parent[index] = index;
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
onEdge[index] = true;
}
}
}
}
}
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void uni(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
// Here, it is treated as rank optimization
parent[rooty] = rootx;
onEdge[rootx] = onEdge[rootx] | onEdge[rooty];// Each time the elements are merged, the relationship between this pile and the boundary is updated
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
onEdge[rooty] = onEdge[rooty] | onEdge[rootx];
} else {
parent[rooty] = rootx;
onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
rank[rootx]++;
}
}
}
bool isOnEdge(int i) {
return onEdge[find(i)];
}
private:
vector<int> parent; // And the necessary of search set
vector<bool> onEdge; // Judge whether it borders
vector<int> rank; // By rank
};
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
UnionFind uf(grid);
// First of all 1 Connect , Then judge whether it borders
// Because the cycle is from top to bottom , From left to right , Therefore, the left and up directions do not need to be considered
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int index = i * n + j;
if (j + 1 < n && grid[i][j + 1] == 1) {
uf.uni(index, index + 1);
}
if (i + 1 < m && grid[i + 1][j] == 1) {
uf.uni(index, index + n);
}
}
}
}
// Judge this 1 Whether it borders the border
int enclaves = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)) {
enclaves++;
}
}
}
return enclaves;
}
};
边栏推荐
- 大学C语言入门到底怎么学才可以走捷径
- 【深度学习】语义分割:论文阅读:(2021-12)Mask2Former
- leetcode-14. Longest common prefix JS longitudinal scanning method
- YARN组织架构
- Meituan Er Mian: why does redis have sentinels?
- [Yu Yue education] reference materials of power electronics technology of Jiangxi University of science and technology
- 软件负载均衡和硬件负载均衡的选择
- Global and Chinese market of AVR series microcontrollers 2022-2028: Research Report on technology, participants, trends, market size and share
- Can I learn PLC at the age of 33
- Elk project monitoring platform deployment + deployment of detailed use (II)
猜你喜欢
Detailed explanation of cookies and sessions
Some thoughts on the study of 51 single chip microcomputer
Nc17 longest palindrome substring
基于B/S的网上零食销售系统的设计与实现(附:源码 论文 Sql文件)
Hero League rotation map automatic rotation
【深度学习】语义分割:论文阅读(NeurIPS 2021)MaskFormer: per-pixel classification is not all you need
Redis distributed lock implementation redison 15 questions
How can I take a shortcut to learn C language in college
Elk project monitoring platform deployment + deployment of detailed use (II)
嵌入式开发比单片机要难很多?谈谈单片机和嵌入式开发设计经历
随机推荐
Teach you how to write the first MCU program hand in hand
五月集训总结——来自阿光
Design and implementation of online snack sales system based on b/s (attached: source code paper SQL file)
Which is the better prospect for mechanical engineer or Electrical Engineer?
O & M, let go of monitoring - let go of yourself
一大波開源小抄來襲
为什么要数据分层
Processes of libuv
[deep learning] semantic segmentation - source code summary
MapReduce working mechanism
One article read, DDD landing database design practice
33岁可以学PLC吗
MySQL数据库优化的几种方式(笔面试必问)
Meituan Er Mian: why does redis have sentinels?
Global and Chinese market of electric pruners 2022-2028: Research Report on technology, participants, trends, market size and share
Redis distributed lock implementation redison 15 questions
Summary of May training - from a Guang
零基础学习单片机切记这四点要求,少走弯路
Solve the problem of too many small files
May brush question 27 - figure