首页>itarticle>[leetcode] problem 200 – number of islands
[leetcode] problem 200 – number of islands
admin11月 13, 20200
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count 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.
int n = grid.length; int m = grid[0].length; boolean[][] visit = newboolean[n][m];
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '1' && !visit[i][j]) { bfs(grid, visit, i, j); count++; } } }
return count; }
privatevoidbfs(char[][] grid, boolean[][] visit, int i, int j){ int n = grid.length; int m = grid[0].length; int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; Queue<int[]> queue = new LinkedList<>(); queue.offer(newint[] {i, j}); visit[i][j] = true;
while (!queue.isEmpty()) { int[] position = queue.poll();
for (int[] direction : directions) { int x = position[0] + direction[0]; int y = position[1] + direction[1];
if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !visit[x][y]) { visit[x][y] = true; queue.offer(newint[] {x, y}); } } } }
近期评论