200 Number of Islands——leetcode
程序员文章站
2022-07-13 12:54:27
...
这个是图像中的填充技术,即选择一个种子,然后对其周边联通的的依次填充。
代码未必最快,但很容易理解。
算法复杂度O(M*N)
空间复杂度O(M*N),最坏情况。
算法说明:
<1>初始化 访问标记
<2>对每一个没有访问的cell,进行填充算法
填充算法:(使用栈)
<1>设置初始种子,入栈
<2>如果栈空,结束
<3>出栈
依次对周围连通的cell,且没有被填充过,入栈
转2。
class Solution {
public:
int numIslands(vector<vector<char>> &grid)
{
if(grid.empty()||grid[0].empty()){
return 0;
}
int scc=0;
const int M=grid.size();
const int N=grid[0].size();
vector<vector<int> > visited(M);
for(int i=0;i<M;i++)
{
visited[i].resize(N);
}
vector<pair<int,int> > s;
for(int i=0;i<M;i++)
{
for(int j=0;j<N;j++)
{
if(!visited[i][j] && grid[i][j]=='1')
{
s.clear();
visited[i][j]=1;
s.push_back(pair<int,int>(i,j));
while(!s.empty())
{
pair<int,int> pr = s.back();
s.pop_back();
int x = pr.first;
int y = pr.second;
x=pr.first-1;
if(x>=0&&grid[x][y]=='1' && !visited[x][y])
{
visited[x][y]=1;
s.push_back(pair<int,int>(x,y));
}
x=pr.first+1;
if(x<M&&grid[x][y]=='1' && !visited[x][y])
{
visited[x][y]=1;
s.push_back(pair<int,int>(x,y));
}
x=pr.first;
y=pr.second-1;
if(y>=0&&grid[x][y]=='1' && !visited[x][y])
{
visited[x][y]=1;
s.push_back(pair<int,int>(x,y));
}
y=pr.second+1;
if(y<N&&grid[x][y]=='1' && !visited[x][y])
{
visited[x][y]=1;
s.push_back(pair<int,int>(x,y));
}
}
++scc;
}
}
}
return scc;
}
};
推荐阅读
-
[leetcode] 306. Additive Number 解题报告
-
LeetCode_#9_回文数 Palindrome Number_C++题解
-
【LeetCode】806. Number of Lines To Write String
-
Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition (python)
-
LeetCode 1020. Number of Enclaves 解题报告(python)
-
Leetcode 1530. Number of Good Leaf Nodes Pairs (python)
-
Leetcode 200. Number of Islands (python+cpp)
-
LeetCode 1254. Number of Closed Islands解题报告(python)
-
【LeetCode】762. Prime Number of Set Bits in Binary Representation
-
LeetCode 5274. Number of Ways to Stay in the Same Place After Some Steps - Java - DP