3554364_ac_375ms_2844k.java

北大大牛代码 1240道题的原代码 超级权威

//package p1414;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private Scanner in;
	private int N, C, max, cnt;
	private int[][] triangle;
	private boolean[][] visited;
	private boolean adj;
	private int[][] mov = new int[][] { { 1, 0 }, { 1, 1 }, { 0, 1 },
			{ 0, -1 }, { -1, 0 }, { -1, -1 } };

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);

		while (true) {
			N = in.nextInt();
			C = in.nextInt();
			if (N == 0 && C == 0) {
				break;
			}
			max = Integer.MIN_VALUE;
			triangle = new int[N][];
			visited = new boolean[N][];
			for (int i = 0; i < N; i++) {
				triangle[i] = new int[i + 1];
				visited[i] = new boolean[i + 1];
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < triangle[i].length; j++) {
					triangle[i][j] = in.nextInt();
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < triangle[i].length; j++) {
					if (triangle[i][j] == 0) {
						triangle[i][j] = C;
						int score = calcScore();
						if (score > max) {
							max = score;
						}
						triangle[i][j] = 0;
					}
				}
			}
			System.out.println(max);
		}

	}

	private int calcScore() {
		int ret = 0;

		for (int i = 0; i < N; i++) {
			Arrays.fill(visited[i], false);
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < triangle[i].length; j++) {
				if (triangle[i][j] != 0 && !visited[i][j]) {
					adj = false;
					cnt = 0;
					floodFill(i, j);
					if (adj) {
						continue;
					}
					if (triangle[i][j] == C) {
						ret -= cnt;
					} else {
						ret += cnt;
					}
				}
			}
		}
		return ret;
	}

	private void floodFill(int i, int j) {
		visited[i][j] = true;
		cnt++;

		for (int l = 0; l < mov.length; l++) {
			int x = i + mov[l][0];
			int y = j + mov[l][1];
			if (!valid(x, y) || visited[x][y]) {
				continue;
			}
			if (triangle[x][y] == 0) {
				adj = true;
			} else {
				if (triangle[x][y] == triangle[i][j]) {
					floodFill(x, y);
				}
			}
		}

	}

	private boolean valid(int i, int j) {
		if (i >= N || i < 0 || j >= triangle[i].length || j < 0) {
			return false;
		}
		return true;
	}

}