岛屿数量
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
代码1 bfs
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));
}
public static int numIslands(char[][] grid) {
// corner case
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int[][] dirs = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int count = 0;
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
LinkedList<int []> queue = new LinkedList<>();
queue.add(new int[]{i, j});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int x = cur[0] + dir[0];
int y = cur[1] + dir[1];
if(x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] =='1'){
grid[x][y] = '0';
queue.add(new int[]{x, y});
}
}
}
}
}
}
return count;
}
}
改版代码
public class Coordinate {
int x,y;
public Coordinate(int x,int y){
this.x = x;
this.y = y;
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @Auther: liuhaidong
* Data: 2019/10/14 0014、16:32
* Description:
* @version: 1.0
*/
public class numIslands {
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));
}
public static int numIslands(char[][] grid) {
if(grid ==null || grid.length ==0 || grid[0].length ==0){
return 0;
}
int islands =0;
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(grid[i][j] == '1'){
bfs(grid,i,j);
islands++;
}
}
}
return islands;
}
private static void bfs(char[][] grid,int x,int y){
int[] diX ={0,0,1,-1};
int[] diY ={1,-1,0,0};
//确认走的四个方向
Queue<Coordinate> queue = new LinkedList<>();
queue.offer(new Coordinate(x,y));
grid[x][y] = '0';
while (!queue.isEmpty()){
Coordinate coordinate = queue.poll();
for (int i = 0; i < 4; i++) {
Coordinate abj = new Coordinate(coordinate.x+diX[i],coordinate.y+diY[i]);
if(!inBound(abj,grid)){
continue;
}
if(grid[abj.x][abj.y] == '1'){
grid[abj.x][abj.y] = '0';
queue.offer(abj);
}
}
}
}
private static boolean inBound(Coordinate coor, char[][] grid) {
int n = grid.length;
int m = grid[0].length;
return coor.x >= 0 && coor.x <n && coor.y >=0 && coor.y <m;
}
}
代码2 dfs
public class Main {
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));
}
public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int num_islands = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
++num_islands;
dfs(grid, i, j);
}
}
}
return num_islands;
}
public static void dfs(char[][] grid, int x, int y) {
int m = grid.length;
int n = grid[0].length;
if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == '0') {
return;
}
grid[x][y] = '0';
dfs(grid, x - 1, y);
dfs(grid, x + 1, y);
dfs(grid, x, y - 1);
dfs(grid, x, y + 1);
}
}
代码3 并查集
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));
}
public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int x = grid.length;
int y = grid[0].length;
int num_islands = 0;
UnionFind uf = new UnionFind(grid);
for (int i = 0; i < x; ++i) {
for (int j = 0; j < y; ++j) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
if (i - 1 >= 0 && grid[i-1][j] == '1') {
uf.union(i * y + j, (i-1) * y + j);
}
if (i + 1 < x && grid[i+1][j] == '1') {
uf.union(i * y + j, (i+1) * y + j);
}
if (j - 1 >= 0 && grid[i][j-1] == '1') {
uf.union(i * y + j, i * y + j - 1);
}
if (j + 1 < y && grid[i][j+1] == '1') {
uf.union(i * y + j, i * y + j + 1);
}
}
}
}
return uf.getCount();
}
public class UnionFind {
int count;
int[] parent;
int[] rank;
public UnionFind(char[][] grid) {
// for problem 200
count = 0;
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent[i * n + j] = i * n + j;
++count;
}
rank[i * n + j] = 0;
}
}
}
//查找对应节点的根节点
public int find(int i) {
if (parent[i] != i){
parent[i] = find(parent[i]);
}
return parent[i];
}
public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx; rank[rootx] += 1;
}
--count;
}
}
public int getCount() {
return count;
}
}
京公网安备 11010502036488号