深度优先搜索及广度优先搜索针对《啊哈，算法》中的宝岛探险的算法练习

FloodFill.java

public class FloodFill {

    private final static int[][] data = new int[][]{
            {1, 2, 1, 0, 0, 0, 0, 0, 2, 3},
            {3, 0, 2, 0, 1, 2, 1, 0, 1, 2},
            {4, 0, 2, 0, 1, 2, 1, 2, 0, 1},
            {3, 2, 0, 0, 0, 2, 1, 2, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 2, 5, 0},
            {0, 1, 2, 1, 0, 1, 1, 2, 5, 0},
            {0, 1, 2, 1, 3, 1, 1, 2, 5, 0},
            {0, 0, 2, 1, 3, 1, 1, 2, 0, 0},
            {0, 0, 0, 1, 3, 1, 6, 0, 1, 2},
            {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
    };

    private static final int[][] book = new int[10][10];

    private static final int width = 10;
    private static final int height = 10;

    private static final int[][] next = new int[][]{
            {0, 1}, // 向右
            {1, 0}, // 向上
            {0, -1}, // 向左
            {-1, 0}, // 向下
    };

    private static void dfsAlgorithm() {

        int color = 0;

        // 枚举所有的点，并为所有可以延伸的点进行标记
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (data[i][j] > 0) {
                    book[i][j] = 1;
                    dfs(i, j, --color);
                }

                System.out.print(data[i][j] + "\t\t");
            }

            System.out.println();
        }
    }

    private static void dfs(int x, int y, int color) {

        // 对符合的点进行标记
        data[x][y] = color;

        for (int i = 0; i < 4; i++) { // 以此点为中心朝上下左右四个方向进行延伸

            int tx = x + next[i][0]; // 必须是新建变量不可使用 x = x + next[i][0]
            int ty = y + next[i][1];

            if (tx < 0 || ty < 0 || tx >= width || ty >= height) { // 判断边界
                continue;
            }

            if (data[tx][ty] > 0 && book[tx][ty] == 0) { // 查找符合要求的点
                book[tx][ty] = 1; // 标记这个点已经查找过
                dfs(tx, ty, color);
            }
        }
    }

    private static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static void bfsAlgorithm() {
        int color = 0;

        // 枚举所有的点，并为所有可以延伸的点进行标记
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (data[i][j] > 0) {
                    book[i][j] = 1;
                    bfs(i, j, --color);
                }

                System.out.print(data[i][j] + "\t\t");
            }

            System.out.println();
        }
    }

    private static void bfs(int x, int y, int color) {
        final Point[] points = new Point[100];
        int head = 0, tail = 0;

        // 将当前标记点入队列
        points[tail++] = new Point(x, y);
        data[x][y] = color;

        while (head != tail) {

            for (int i = 0; i < 4; i++) { // 遍历上下左右朝向
                int tx = points[head].x + next[i][0];
                int ty = points[head].y + next[i][1];

                if (tx < 0 || ty < 0 || tx >= width || ty >= height) { // 检查边界
                    continue;
                }

                if (data[tx][ty] > 0 && book[tx][ty] == 0) { // 符合查询条件的点
                    book[tx][ty] = 1; // 标记查询过得点
                    data[tx][ty] = color;
                    points[tail++] = new Point(tx, ty);
                }
            }

            head++;
        }

    }

    public static void main(String[] args) {

        System.out.println("after dfs: ");
        FloodFill.dfsAlgorithm();

        System.out.println("after bfs: ");
        FloodFill.bfsAlgorithm();
    }
}