Problem: Acwing1113. 红与黑
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
这是一道经典的洪水填充问题,可以使用dfs搜索和bfs搜索来解决。 ′ . ′ : '.' : ′.′:表示黑色瓷砖,‘#’:表示红色瓷砖,‘@’表示黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。我们可以填充所有的黑色瓷砖,然后统计黑色瓷砖的个数。
解题方法
首先,遍历所有的瓷砖记录起始位置,将起始位置’@‘标记为’.‘,便于后面进行计算。
然后从起始位置开始进行dfs,把起始位可以延伸到的位置全部标记成’H’。
最后遍历整块区域统计’H’个数,输出答案即可。
复杂度
时间复杂度:
假设砖块的个数为N,每个砖块最多被遍历4次,所以时间复杂度为 O ( N ) O(N) O(N)。
空间复杂度:
使用了一个二维数组来存储砖块的状态,所以空间复杂度为 O ( N ) 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 stub
if (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;
}
}