解题思路:
遇到一个水洼(W)进行扩散标记为干燥(.) 计数加一(count++)
依次遍历去除
参考代码:
BFS
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 | import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class 水洼_BFS { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); sc.nextLine(); char[][] arr = new char[n][m]; for (int i = 0; i < n; i++) { arr[i] = sc.nextLine().toCharArray(); } int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { //依次找到每一个水洼 if (arr[i][j] == 'W') { //BFS扩散 BFS(arr, i, j); //记录水洼数 count++; } } } System.out.println(count); } //扩散方向 上右下左，左上，右上，左下，右下 八个方向 static int[][] direction = {{0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}, {-1, 0}, {0, -1}}; private static void BFS(char[][] arr, int startx, int starty) { LinkedList<course> queue = new LinkedList<course>(); queue.add(new course(startx, starty));//入队 while (!queue.isEmpty()) { course c = queue.poll();//去除队列中第一个水洼 arr[c.x][c.y] = '.';//去除水洼 for (int k = 0; k < 8; k++) { int x = c.x + direction[k][0]; int y = c.y + direction[k][1]; //边界校验 if (x >= 0 && y >= 0 && x < arr.length && y < arr[0].length && arr[x][y] == 'W') { queue.addLast(new course(x,y));//添加一下个水洼 } } } }}class course { public int x;//行号 public int y;//列号 public course(int x, int y) { this.x = x; this.y = y; }} |
DFS
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 | import java.util.Scanner;public class 水洼_DFS { //水洼 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); sc.nextLine(); char[][] arr = new char[n][m]; for (int i = 0; i < n; i++) { arr[i] = sc.nextLine().toCharArray(); } int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { //依次找到每一个水洼 if (arr[i][j] == 'W') { //DFS扩散 dfs(i, j, arr); //记录水洼数 count++; } } } System.out.println(count); } //扩散方向 上右下左，左上，右上，左下，右下 八个方向 static int[][] direction = {{0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}, {-1, 0}, {0, -1}}; private static void dfs(int i, int j, char[][] arr) { arr[i][j] = '.';//去除水洼 for (int k = 0; k < 8; k++) { int x = i + direction[k][0]; int y = j + direction[k][1]; //边界校验 if (x >= 0 && y >= 0 && x < arr.length && y < arr[0].length && arr[x][y] == 'W') { dfs(x, y, arr); } } }} |
9.9 分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复