Acwing1113. 红与黑

Problem: Acwing1113. 红与黑

思路

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

解题方法

首先，遍历所有的瓷砖记录起始位置，将起始位置’@‘标记为’.‘,便于后面进行计算。
然后从起始位置开始进行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 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;
	}

}