글 읽기 - 2%에서 틀렸다고 나옵니다 ㅠ 반례 부탁드립니다.(자바)

bravery0730 3년 전 0

테스트케이스와 게시판에 올라온 반례 모두 맞지만 2%에서 틀렸다고 합니다ㅠ.. 반례 부탁드리겠습니다.

public class Main {
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int[][] map;
	static boolean[][] visited;
	static int N, L, R, row;

	public static void main(String[] args) throws Exception {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] strings = br.readLine().split(" ");
		N = Integer.parseInt(strings[0]);
		L = Integer.parseInt(strings[1]);
		R = Integer.parseInt(strings[2]);
		row = N + (N - 1);
		map = new int[row][row];

		for (int i = 0; i < row; i += 2) {
			String[] strs = br.readLine().split(" ");
			int idx = 0;

			for (int j = 0; j < row; j += 2) {
				map[i][j] = Integer.parseInt(strs[idx]);
				idx++;
			}
		}

		int cnt = 0;
		while (true) {
			visited = new boolean[row][row];

			if (openBarrier()) {
				for (int i = 0; i < row; i += 2) {
					for (int j = 0; j < row; j += 2) {
						if (!visited[i][j]) {
							visited[i][j] = true;
							bfs(i, j);
						}
					}
				}

			} else {
				break;
			}

			cnt++;
		}

		bw.write(Integer.toString(cnt));
		bw.flush();
		bw.close();
		br.close();
	}

	public static void bfs(int x, int y) {
		Queue<Pair> q = new LinkedList<>();
		ArrayList<Pair> country = new ArrayList<>();
		country.add(new Pair(x, y));
		q.add(new Pair(x, y));

		int sum = map[x][y];
		while (!q.isEmpty()) {
			Pair pair = q.poll();

			for (int i = 0; i < 4; i++) {
				int nx = pair.x + dx[i];
				int ny = pair.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= row || ny >= row) {
					continue;
				}
				if (map[nx][ny] == Integer.MAX_VALUE) {
					continue;
				}

				if (!visited[nx][ny]) {
					visited[nx][ny] = true;
					q.add(new Pair(nx, ny));
					if (map[nx][ny] != 0) {

						sum += map[nx][ny];
						country.add(new Pair(nx, ny));
					}
				}
			}
		}
		for (int i = 0; i < country.size(); i++) {
			Pair p = country.get(i);
			map[p.x][p.y] = sum / country.size();
		}
	}

	public static boolean openBarrier() {

		boolean flag = false;

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < row; j++) {
				if (i % 2 == 0 && j % 2 != 0) {
					int num = Math.abs(map[i][j - 1] - map[i][j + 1]);

					if (num >= L && num <= R) {
						flag = true;
						map[i][j] = 0;
					} else
						map[i][j] = Integer.MAX_VALUE;
				} else if (i % 2 != 0 && j % 2 == 0) {
					int num = Math.abs(map[i - 1][j] - map[i + 1][j]);

					if (num >= L && num <= R) {
						flag = true;
						map[i][j] = 0;
					} else
						map[i][j] = Integer.MAX_VALUE;
				}
			}
		}
		

		if (flag)
			return true;
		else
			return false;
	}

	static class Pair {
		int x;
		int y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2%에서 틀렸다고 나옵니다 ㅠ 반례 부탁드립니다.(자바)

bravery0730 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말