글 읽기 - 반례 도와주세요!

dyj07132 2년 전 0

도저히 반례를 못찾겠어서 여쭤봅니다.

아예 시작도 안하고 틀렸습니다가 나옵니다.

bfs를 사용해서 1과 인접한 0에 모양의 크기만큼 더해주어 그중 가장 큰 수를 출력했습니다.

import java.util.*;
import java.io.*;
class pair {
	int x, y;
	pair(int x, int y){
		this.x=x;
		this.y=y;
	}
}
public class Main{
	static int n,m;
	static int[][] a = new int[1001][1001];
	static int[][] check = new int [1001][1001];
	static int[][] ans = new int[1001][1001];
	
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static int index=0;
	static void bfs(int sx, int sy) {
		int size=1;
		Queue<pair> q = new LinkedList<>();
		q.add(new pair(sx, sy));
		check[sx][sy]=1;
		ArrayList<pair> aa = new ArrayList<>();
		while(!q.isEmpty()) {
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(0<=nx&&nx<n&&0<=ny&&ny<m) {
					if(check[nx][ny]==0&&a[nx][ny]==1) {
						check[nx][ny]=1;
						q.add(new pair(nx, ny));
						size+=1;
					}
					if(check[nx][ny]<=index&&a[nx][ny]==0) {
						check[nx][ny]+=1;
						aa.add(new pair(nx, ny));
					}
				}
			}
		}
		for (int i = 0; i < aa.size(); i++) {
			
				ans[aa.get(i).x][aa.get(i).y]+=size;	
			
		}
	}
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		   String[] t  = br.readLine().split(" ");
		   n = Integer.parseInt(t[0]);
	        m = Integer.parseInt(t[1]);
		for (int i = 0; i < n; i++) {
			String[] s = br.readLine().split(" ");
			for (int j = 0; j < m; j++) {
				a[i][j]=Integer.parseInt(s[j]);
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(a[i][j]==1) {
					if(check[i][j]==0) {
						bfs(i, j);
						index++;
					}
				}
			}
		}
		int max=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(ans[i][j]>max) {
					max=ans[i][j];
				}
			}
		}
		System.out.println(max+1);
		
	}
	
}

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

문제

문제

출처

ICPC

반례 도와주세요!

dyj07132 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말