Created
June 27, 2018 05:42
-
-
Save zhgqthomas/2320988394dd02529d5befe8b47b70a0 to your computer and use it in GitHub Desktop.
深度优先搜索及广度优先搜索针对《啊哈,算法》中的宝岛探险的算法练习
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment