1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
| import java.util.HashSet; import java.util.LinkedList; import java.util.Set;
public class NumIslands {
int nums = 0; int[][] a = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; LinkedList<Node> queue = new LinkedList<>(); Set<Node> used = new HashSet<>();
public int numIslands(char[][] grid) { int rows = grid.length; if (rows == 0) { return 0; } int cols = grid[0].length; for (int row = 0; row < rows; row ++) { for (int col = 0; col < cols; col ++) { if (grid[row][col] == '1') { bfs(grid, row, col, rows, cols); nums += 1; } } } return nums; }
public void bfs(char[][] grid, int row, int col, int rows, int cols) { grid[row][col] = '2'; queue.clear(); used.clear(); Node root = new Node(row, col); queue.add(root); used.add(root); while (!queue.isEmpty()) { int size = queue.size(); while (size > 0) { size --; Node cur = queue.removeFirst(); int preX = cur.x; int preY = cur.y; for (int i = 0; i < a.length; i ++) { int nX = preX + a[i][0]; int nY = preY + a[i][1];
if (nX < 0 || nY < 0 || nX >= rows || nY >= cols) { continue; }
if (grid[nX][nY] != '1') { continue; }
grid[nX][nY] = '2';
Node node = new Node(nX, nY); if (!used.contains(node)) { queue.add(node); } } } } }
private static class Node { int x; int y; Node(int x, int y) { this.x = x; this.y = y; }
@Override public boolean equals(Object o) { Node t = (Node) o; return x == t.x && y == t.y; }
@Override public int hashCode() { return 1; } }
public static void main(String[] args) { char[][] grid = new char[][]{ {'1','1','1','1','0'}, {'1','1','0','1','0'}, {'1','1','0','0','0'}, {'0','0','0','0','0'} }; NumIslands nIslands = new NumIslands(); System.out.println(nIslands.numIslands(grid)); }
}
|