class Solution {
public:
void DFS(int i ,int j,vector<vector<int>>&arr,int n,int m,int color){
arr[i][j]=color;
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={0,-1,1,-1,1,-1,0,1};
for(int k=0;k<8;k++){
int r=i+dx[k];
int c=j+dy[k];
if(r>=0&&r<n&&c>=0&&c<m&&arr[r][c]==1){
DFS(r,c,arr,n,m,color);
}
}
/* int rnxt=i+1;
int rpre=i-1;
int cnxt=j+1;
int cpre=j-1;
if(rnxt>=0&&rnxt<n){
if(cnxt>=0&&cnxt<m&&arr[rnxt][cnxt]==1)DFS(rnxt,cnxt,arr,n,m,color);
if(cpre>=0&&cpre<m&&arr[rnxt][cpre]==1)DFS(rnxt,cpre,arr,n,m,color);
if(arr[rnxt][j]==1)DFS(rnxt,j,arr,n,m,color);
}
if(rpre>=0&&rpre<n){
if(cnxt>=0&&cnxt<m&&arr[rpre][cnxt]==1)DFS(rpre,cnxt,arr,n,m,color);
if(cpre>=0&&cpre<m&&arr[rpre][cpre]==1)DFS(rpre,cpre,arr,n,m,color);
if(arr[rpre][j]==1)DFS(rpre,j,arr,n,m,color);
}
if(cnxt>=0&&cnxt<m&&arr[i][cnxt]==1)DFS(i,cnxt,arr,n,m,color);
if(cpre>=0&&cpre<m&&arr[i][cpre]==1)DFS(i,cpre,arr,n,m,color);
}*/
}
int countIslands(vector<vector<char>> grid) {
// Code here
int n=grid.size();
int m=grid[0].size();
vector<vector<int>>arr(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='L'){
arr[i][j]=1;
}else arr[i][j]=0;
}
}
int color=2;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]==1){
DFS(i,j,arr,n,m,color);
color++;
}
}
}
int noc=0;
unordered_map<int,int>mp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]){
if(!mp[arr[i][j]]){
noc++;
mp[arr[i][j]]=1;
}
}
}
}
return noc;
}
};
No comments:
Post a Comment