Wednesday, June 10, 2015

UVa 572 - Oil Deposits

// UVa 572 - Oil Deposits
import java.util.Scanner;

public class Main {
	static int m;
	static int n;
	static boolean[][] oil = new boolean[100][100];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		m = in.nextInt();
		n = in.nextInt();

		while (m != 0 && n != 0) {
			in.nextLine();
			for (int i = 0; i < m; i++) {
				String line = in.nextLine();
				for (int j = 0; j < line.length(); j++)
					oil[i][j] = line.charAt(j) == '@';
			}

			int sol = 0;

			for (int i = 0; i < m; i++)
				for (int j = 0; j < n; j++)
					if (oil[i][j]) {
						sol++;
						dfs(i, j);
					}

			System.out.println(sol);
			m = in.nextInt();
			n = in.nextInt();
		}
	}

	public static void dfs(int a, int b) {
		oil[a][b] = false;
		if (a > 0 && oil[a - 1][b])
			dfs(a - 1, b);
		if (b > 0 && oil[a][b - 1])
			dfs(a, b - 1);
		if (a < m - 1 && oil[a + 1][b])
			dfs(a + 1, b);
		if (b < n - 1 && oil[a][b + 1])
			dfs(a, b + 1);

		if (a > 0 && b > 0 && oil[a - 1][b - 1])
			dfs(a - 1, b - 1);
		if (a > 0 && b < n - 1 && oil[a - 1][b + 1])
			dfs(a - 1, b + 1);
		if (a < m - 1 && b > 0 && oil[a + 1][b - 1])
			dfs(a + 1, b - 1);
		if (a < m - 1 && b < n - 1 && oil[a + 1][b + 1])
			dfs(a + 1, b + 1);

	}

}

No comments:

Post a Comment