글 읽기 - 반례나 지적 좀 부탁드립니다

jkhb62012 2년 전 0

제가 이 글을 쓰기까지 질문게시판 내에 존재하는 모든 반례 다 맞습니다.

제출해도 딱 95%에서 틀리더라고요. 게시판 반례도 다 맞고 95%까지 간 거 보면 대부분은 다 맞는 것 같은데 왜 틀렸는지 반례를 못찾겠습니다

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int N,M,init,ans;
	private static char[][] map;
	private static ArrayList<CCTV> cctv;
	private static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		cctv = new ArrayList<>();
		init = ans = N*M;
		
		for(int i = 0; i < N; i++) {
			char[] tmp = br.readLine().toCharArray();
			for(int j = 0; j < M; j++) {
				map[i][j] = tmp[2*j];
				if(map[i][j]-'0' > 0 && map[i][j]-'0' < 6) {
					cctv.add(new CCTV(j,i,map[i][j]-'0'));
					map[i][j] = '#';
					init--;
				}
				else if(map[i][j] == '6')
				init--;
			}
		}
		
		for(int i = 0; i < cctv.size(); i++) {
			CCTV tmp = cctv.get(i);
			
			if(tmp.getType() == 5) {
				int x = tmp.getX();
				int y = tmp.getY();
				
				dir : for(int j = 0; j < dir.length; j++) {
					int nextX = x+dir[j][1];
					int nextY = y+dir[j][0];
					
					for(; nextX>=0&&nextY>=0&&nextX<M&&nextY<N;
							nextX=nextX+dir[j][1], nextY=nextY+dir[j][0]) {
						if(map[nextY][nextX] == '6')
							continue dir;
						else if(map[nextY][nextX] == '0') {
							map[nextY][nextX] = '#';
							init--;
						}
					}
				}
				
				cctv.remove(i);
				i--;
			}
		}
		
		ans = init;
		int[] index = new int[cctv.size()];
		
		if(cctv.size() != 0)
				checkSpace(index);
		
		System.out.println(ans);
	}
	
	private static void checkSpace(int[] index) {
		for(int k = 0; k < Math.pow(4, index.length)-1; k++) {
			char[][] tmp = new char[N][M];
			int num = init;
			
			for(int i = 0; i < N; i++) {
				tmp[i] = Arrays.copyOf(map[i], M);
			}
			
			for(int i = 0; i < cctv.size(); i++) {
				int type = cctv.get(i).getType();
				int x = cctv.get(i).getX();
				int y = cctv.get(i).getY();
                if(type == 2 && index[i] > 1)
                    continue;
				num = findMap(tmp,index[i],x,y,num);
				int idx;
				
				switch(type) {
				case 2:
					idx = index[i]+2;
					num = findMap(tmp,idx,x,y,num);
					break;
				case 3:
					idx = index[i]-1 >= 0? index[i]-1 : 3;
					num = findMap(tmp,idx,x,y,num);
					break;
				case 4:
					idx = index[i]-1 >= 0? index[i]-1 : 3;
					num = findMap(tmp,idx,x,y,num);
					idx = index[i]+1 < 4? index[i]+1 : 0;
					num = findMap(tmp,idx,x,y,num);
					break;
				default:
					break;
				}
			}
			
			index[0]++;
			if(index[0] >= 4) {
				index[0] = 0;
				int idx = 1;
				while(idx < index.length) {
					index[idx]++;
					if(index[idx] >= 4) {
						index[idx] = 0;
						idx++;
					}
					else
						break;
				}
			}
			
			if(num < ans)
				ans = num;
		}
	}
	
	private static int findMap(char[][] map, int idx, int x, int y, int num) {
		int nextX = x+dir[idx][1];
		int nextY = y+dir[idx][0];
		while(nextX>=0&&nextY>=0&&nextX<M&&nextY<N) {
			if(map[nextY][nextX] == '0') {
				num--;
				map[nextY][nextX] = '#';
			}
			else if(map[nextY][nextX] == '6')
				break;
			
			nextX += dir[idx][1];
			nextY += dir[idx][0];
		}
		
		return num;
	}
}

class CCTV {
	private int x,y,type;
	
	CCTV(int x, int y, int type) {
		this.x = x;
		this.y = y;
		this.type = type;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public int getType() {
		return type;
	}

	public void setType(int type) {
		this.type = type;
	}
}

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

문제

문제

출처

ICPC

반례나 지적 좀 부탁드립니다

jkhb62012 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말