Given an
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
m x n
2d grid
map of '1'
s (land) and '0'
s (water), return the number of islands.An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
Output: 1
Approach
Java
public class NumberOfIslands {public static void main(String[] args) {char[][] grid = { { '1', '1', '1', '1', '0' },{ '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' },{ '0', '0', '0', '0', '0' } };System.out.println(numIslands(grid));}static int numIslands(char[][] grid) {int n = grid.length;if (n == 0)return 0;int num_islands = 0;int m = grid[0].length;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '1') {dfs(grid, i, j, n, m);num_islands += 1;}}}return num_islands;}static void dfs(char[][] grid, int i, int j, int n, int m) {// check if cell is valid or notif (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0')return;grid[i][j] = '0';// call for all four directionsdfs(grid, i + 1, j, n, m);dfs(grid, i - 1, j, n, m);dfs(grid, i, j + 1, n, m);dfs(grid, i, j - 1, n, m);}}
C++
#include <bits/stdc++.h>using namespace std;void dfs(vector<vector<char>> &grid, int i, int j, int n, int m){//check if cell is valid or notif (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0')return;grid[i][j] = '0';//call for all four directionsdfs(grid, i + 1, j, n, m);dfs(grid, i - 1, j, n, m);dfs(grid, i, j + 1, n, m);dfs(grid, i, j - 1, n, m);}int numIslands(vector<vector<char>> &grid){int n = grid.size();if (n == 0)return 0;int num_islands = 0;int m = grid[0].size();for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (grid[i][j] == '1'){dfs(grid, i, j, n, m);num_islands += 1;}}}return num_islands;}int main(){vector<vector<char>> grid = {{'1', '1', '1', '1', '0'},{'1', '1', '0', '1', '0'},{'1', '1', '0', '0', '0'},{'0', '0', '0', '0', '0'}};cout << numIslands(grid);return 0;}
No comments:
Post a Comment