Acwing1113. 红与黑

2024-03-21 21:36

文章标签 红与黑 acwing1113

本文主要是介绍Acwing1113. 红与黑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: Acwing1113. 红与黑

文章目录

思路
解题方法
复杂度
Code

思路

这是一道经典的洪水填充问题，可以使用dfs搜索和bfs搜索来解决。 $^{'} .^{'} :$ 表示黑色瓷砖，‘#’:表示红色瓷砖，‘@’表示黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。我们可以填充所有的黑色瓷砖，然后统计黑色瓷砖的个数。

解题方法

首先，遍历所有的瓷砖记录起始位置，将起始位置’@‘标记为’.‘,便于后面进行计算。
然后从起始位置开始进行dfs，把起始位可以延伸到的位置全部标记成’H’。
最后遍历整块区域统计’H’个数，输出答案即可。

复杂度

时间复杂度:

假设砖块的个数为N，每个砖块最多被遍历4次，所以时间复杂度为 $O (N)$ 。

空间复杂度:

使用了一个二维数组来存储砖块的状态，所以空间复杂度为 $O (N)$ 。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = 25;static char[][] matrix = new char[MAXN][MAXN];static int w, h;public static void main(String[] args) throws IOException {while (true) {w = nextInt();h = nextInt();if(w == 0 || h == 0) {return;}
// 			in.readLine();for (int i = 0; i < h; i++) {matrix[i] = in.readLine().toCharArray();}int sx = 0;int sy = 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (matrix[i][j] == '@') {sx = i;sy = j;matrix[i][j] = '.';}}}dfs(sx, sy); // 对所有的黑色砖块进行填充 'H'int res = 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (matrix[i][j] == 'H') {res++;}}}out.println(res);out.flush();}}private static void dfs(int sx, int sy) {// TODO Auto-generated method stubif (sx < 0 || sx >= h || sy < 0 || sy >= w || matrix[sx][sy] != '.') {return;}matrix[sx][sy] = 'H';dfs(sx + 1, sy);dfs(sx - 1, sy);dfs(sx, sy + 1);dfs(sx, sy - 1);}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}