To solve LeetCode question 200, there is already one good explanation of how to solve it.
The basic idea is to use tree traverse algorithm (dfs or bfs) to check the adjacent land.
Here is my Javascript solution:
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let count = 0;
if (grid == null || grid.length === 0) {
return 0;
}
let row = grid.length;
let col = grid[0].length;
function dfs(i, j) {
if (i > row - 1 || j > col -1 || i< 0 || j < 0) {
return;
}
if (grid[i][j] === "1") {
grid[i][j] = "0";
dfs(i+1,j); //down
dfs(i,j+1); //right
dfs(i-1,j); //up
dfs(i,j-1); //left
}
}
for (let i=0; i<row; i++) {
for (let j=0; j<col; j++) {
if (grid[i][j] === "1") {
grid[i][j] = "0";
dfs(i+1,j); //down
dfs(i,j+1); //right
dfs(i-1,j); //up
dfs(i,j-1); //left
count++;
}
}
}
return count;
};
var grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
];
console.log(result = numIslands(grid));
console.assert(result === 1);
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
];
console.log(result = numIslands(grid));
console.assert(result === 3);
grid = [
["1","1","1"],
["0","1","0"],
["1","1","1"]
];
console.log(result = numIslands(grid));
console.assert(result === 1);
No comments:
Post a Comment