理财网网站开发源码h5,专业做网站的企业,厦门网站建设电话,专门做拼团的网站宝岛探险问题
问题描述#xff1a;某片海域有诸多岛屿#xff0c;用0表示海洋#xff0c;1-9表示陆地#xff0c;现给定一个岛屿上的坐标点#xff0c;求解所在岛屿的面积
思路#xff1a;显然这是一个搜索算法#xff0c;即只要从当前坐标点开始遍历#xff0c;每遍…宝岛探险问题
问题描述某片海域有诸多岛屿用0表示海洋1-9表示陆地现给定一个岛屿上的坐标点求解所在岛屿的面积
思路显然这是一个搜索算法即只要从当前坐标点开始遍历每遍历到一个点进行计数即可但是要注意sum的初始值为1
Input 10 10 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0 6 8
Output 38
DFS
import java.util.Scanner;public class DFS {static int[][] a new int[50][50];static int[][] book new int[50][50];static int sum 1;static int n, m;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 0; i n; i) {for (int j 0; j m; j) {a[i][j] input.nextInt();}}int startX input.nextInt();int startY input.nextInt();book[startX][startY] 1;dfs(startX, startY);System.out.println(sum);}public static void dfs(int x, int y) {int[][] next {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int tx, ty;for (int i 0; i 4; i) {tx x next[i][0];ty y next[i][1];if(tx 0 || tx n - 1 || ty 0 || ty n - 1) {continue;}if (a[tx][ty] 0 book[tx][ty] 0) {sum ;book[tx][ty] 1;dfs(tx, ty);}}return;}
}BFS
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;class node {int x;int y;node(int x, int y) {this.x x;this.y y;}
}
public class BFS {static int[][] a new int[50][50];static int[][] book new int[50][50];static int n, m;static int sum 1;static Queuenode queue new LinkedList();static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 0; i n; i) {for (int j 0; j m; j) {a[i][j] input.nextInt();}}int startX input.nextInt();int startY input.nextInt();queue.offer(new node(startX, startY));book[startX][startY] 1;bfs();System.out.println(sum);}public static void bfs() {int[][] next {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int tx, ty;while (!queue.isEmpty()) {for (int i 0; i 4; i) {tx queue.peek().x next[i][0];ty queue.peek().y next[i][1];if (tx 0 || tx n - 1 || ty 0 || ty n - 1) {continue;}if(a[tx][ty] 0 book[tx][ty] 0) {queue.offer(new node(tx, ty));sum;book[tx][ty] 1;}}queue.remove();}return;}
}拓展漫水填充法FloodFill 问题 要求解区域中总共有多少岛屿 思路对每个点进深搜对于每个大于0的点进行填充负值负值每次-1最后输出正的这个值即是岛屿个数。 Input: 10 10 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0 Output:
import java.util.Scanner;public class DFS {static int[][] a new int[50][50];static int[][] book new int[50][50];static int sum 1;static int num 0;static int n, m;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 0; i n; i) {for (int j 0; j m; j) {a[i][j] input.nextInt();}}for (int i 0; i n; i) {for (int j 0; j m; j) {if (a[i][j] 0) {num--;book[i][j] 1;dfs(i, j, num);}}}for (int i 0; i n; i) {for (int j 0; j m; j) {System.out.print(a[i][j] \t);}System.out.println();}System.out.println(-num);}public static void dfs(int x, int y, int color) {int[][] next {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int tx, ty;a[x][y] color;for (int i 0; i 4; i) {tx x next[i][0];ty y next[i][1];if(tx 0 || tx n - 1 || ty 0 || ty n - 1) {continue;}if (a[tx][ty] 0 book[tx][ty] 0) {sum ;book[tx][ty] 1;dfs(tx, ty, color);}}return;}
}
