- 1 import java.util.ArrayDeque;
- 2 import java.util.Deque;
- 3 4 public class numberOfIslandBFS {
- 5 6 public static void main(String[] args) {
- 7 char[][] grid = new char[][] {
- 8 {
- '0',
- '1',
- '1',
- '0'
- },
- 9 {
- '1',
- '0',
- '0',
- '1'
- },
- 10 {
- '1',
- '0',
- '0',
- '1'
- },
- 11 {
- '1',
- '1',
- '0',
- '0'
- }
- };
- 12 System.out.println("#islands=" + new Solution().numIslands(grid));
- 13 14
- }
- 15 16 private static class Point {
- 17 int x;
- 18 int y;
- 19 20 Point(int x, int y) {
- 21 this.x = x;
- 22 this.y = y;
- 23
- }
- 24
- }
- 25 26 public static class Solution {
- 27 public int numIslands(char[][] grid) {
- 28 int res = 0;
- 29
- if (grid == null || grid.length == 0 || grid[0].length == 0) {
- 30
- return 0;
- 31
- }
- 32 33 int row = grid.length;\\row和col主要用来设置
- for循环的边界34 int col = grid[0].length;
- 35 36 boolean[][] visited = new boolean[row][col];
- 37 int[][] directions = {
- 38 {
- 1,
- 0
- },
- 39 { - 1,
- 0
- },
- 40 {
- 0,
- 1
- },
- 41 {
- 0,
- -1
- }
- };
- 42 Deque queue = new ArrayDeque();
- 43 44
- for (int i = 0; i < row; i++) {
- 45
- for (int j = 0; j < col; j++) {
- 46
- if (grid[i][j] == '0' || visited[i][j]) {
- 47
- continue;
- 48
- }
- 49 50 queue.add(new Point(i, j));
- 51 res += 1;
- 52
- while (!queue.isEmpty()) {
- 53 Point cur = queue.poll(); // queue =[ (1,1) ]
- 54 int tpx = cur.x; // 1,用来记录弹出后的x,y
- 55 int tpy = cur.y; // 1
- 56 57 visited[tpx][tpy] = true; //并且标记为已访问
- 58
- for (int k = 0; k < 4; k++) {
- 59 int x = tpx + directions[k][0]; // 0
- 60 int y = tpy + directions[k][1]; // 1
- 61 62
- if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1'63 && !visited[x][y]) {
- 64 queue.add(new Point(x, y));
- 65
- }
- 66
- }
- 67
- }
- 68
- }
- 69
- }
- 70 71
- return res;
- 72
- }
- 73 74
- }
- 75 76
- }
来源: http://www.cnblogs.com/zuofeiyi/p/6477276.html