Created
April 17, 2020 13:58
-
-
Save SuryaPratapK/a494ad5194ea33ee83b343698c1fa98e to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| void mark_current_island(vector<vector<char>> &matrix,int x,int y,int r,int c) | |
| { | |
| if(x<0 || x>=r || y<0 || y>=c || matrix[x][y]!='1') //Boundary case for matrix | |
| return; | |
| //Mark current cell as visited | |
| matrix[x][y] = '2'; | |
| //Make recursive call in all 4 adjacent directions | |
| mark_current_island(matrix,x+1,y,r,c); //DOWN | |
| mark_current_island(matrix,x,y+1,r,c); //RIGHT | |
| mark_current_island(matrix,x-1,y,r,c); //TOP | |
| mark_current_island(matrix,x,y-1,r,c); //LEFT | |
| } | |
| public: | |
| int numIslands(vector<vector<char>>& grid) { | |
| //For FAST I/O | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| int rows = grid.size(); | |
| if(rows==0) //Empty grid boundary case | |
| return 0; | |
| int cols = grid[0].size(); | |
| //Iterate for all cells of the array | |
| int no_of_islands = 0; | |
| for(int i=0;i<rows;++i) | |
| { | |
| for(int j=0;j<cols;++j) | |
| { | |
| if(grid[i][j]=='1') | |
| { | |
| mark_current_island(grid,i,j,rows,cols); | |
| no_of_islands += 1; | |
| } | |
| } | |
| } | |
| return no_of_islands; | |
| } | |
| }; |
Awesome, thank you
I also did it <3
amazing !
time saving code for mark_current_islands() function 😉
void mark_current_islands(vector<vector> &g, int i, int j, int rows, int cols)
{
//boundary case!!
if(i<0 || i> rows || j<0 || j> cols || g[i][j]!= '1') return;
g[i][j]= '2'; //visited!!
int r[] = {1,-1,0,0};
int c[] = {0,0,1,-1};
for(int k=0; k<4; k++)
{
mark_current_islands(g, i + r[k], j + c[k], rows, cols);
}
}
we can also do it by BFS, I saw neetcode video.
Perfect Explanation "Here is the Py Code for Folks "
class Solution:
def mark_current_island(self, matrix, x, y, r, c):
if x < 0 or x >= r or y < 0 or y >= c or matrix[x][y] != '1':
return
# Mark current cell as visited
matrix[x][y] = '2'
# Make recursive call in all 4 adjacent directions
self.mark_current_island(matrix, x + 1, y, r, c) # DOWN
self.mark_current_island(matrix, x, y + 1, r, c) # RIGHT
self.mark_current_island(matrix, x - 1, y, r, c) # TOP
self.mark_current_island(matrix, x, y - 1, r, c) # LEFT
def numIslands(self, grid):
rows = len(grid)
if rows == 0: # Empty grid boundary case
return 0
cols = len(grid[0])
# Iterate for all cells of the array
no_of_islands = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
self.mark_current_island(grid, i, j, rows, cols)
no_of_islands += 1
return no_of_islands
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Awesome solution, applying DFS is great idea. Keep posting videos and tutorials as they are really helpful.
Wishing exponential success to you and your channel.