글 읽기 - 반례나 틀린부분 찾아주시면 감사하겠습니다!! ㅠㅠ

sehlryn7 4년 전 0

테케나 반례 찾아서 실행해도 답이 맞게 나오는데

혹시 반례찾으시거나 틀린부분 찾으시면 알려주세요 ㅠㅠ

import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N,M,cnt=0;
	static int Rx, Ry, Bx, By, Hx, Hy;
	static int[] nx = {0,1,0,-1},ny = {-1,0,1,0};
	static boolean cntinsert = false, done = false;
	static Queue<Node> q = new LinkedList<>();
	static int[][] Map;
	public static void main(String[] args) throws Exception{
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Map = new int[N][M];
		boolean[][][][] Rchk = new boolean[N][M][N][M];
		for(int i=0; i<N; i++) {
			String st = br.readLine();
			for(int j=0; j<M; j++) {
				Map[i][j] = st.charAt(j);
				if(Map[i][j]=='O') {
					Hy = i; Hx = j;
				}
				else if(Map[i][j]=='B') {
					By = i; Bx = j;
				}
				else if(Map[i][j]=='R') {
					Ry = i; Rx = j;
				}
			}
		}
		q.add(new Node(Rx,Ry,Bx,By));
		FindWay(Rchk,cnt);	
		if(cnt>10||cnt==0) bw.append(String.valueOf(-1));
		else bw.append(String.valueOf(cnt));
		bw.flush();
		bw.close();
	}
	public static void FindWay(boolean[][][][] Rchkmap, int tcnt) throws IOException {
		Node tmp = q.poll();
		int rx = tmp.rx, ry = tmp.ry, bx = tmp.bx, by = tmp.by;
		int tmpcnt = tcnt+1;
		if(tmpcnt>10) return;
		for(int i=0; i<4; i++) {
			int tmpbx = bx,tmpby = by,tmprx = rx,tmpry = ry;
			if(tmprx+nx[i]>=0&&tmpry+ny[i]>=0&&tmprx+nx[i]<M&&tmpry+ny[i]<N&&Rchkmap[tmpry+ny[i]][tmprx+nx[i]][tmpby+ny[i]][tmpbx+nx[i]]==false) {  //&&Bchkmap[tmpby+ny[i]][tmpbx+nx[i]]==false
				while(true) {
					if(tmprx+nx[i]>=0&&tmpry+ny[i]>=0&&tmprx+nx[i]<M&&tmpry+ny[i]<N) {
						if(Map[tmpry+ny[i]][tmprx+nx[i]]!='#') {
							if(Map[tmpry+ny[i]][tmprx+nx[i]]=='O') {
								done = true;
								break;
							}
							else {
								tmprx += nx[i];
								tmpry += ny[i];
							}
						}
						else break;
					}
					else break;
				}
				while(true) {
					if(tmpbx+nx[i]>=0&&tmpby+ny[i]>=0) {
						if(Map[tmpby+ny[i]][tmpbx+nx[i]]!='#') {
							if(Map[tmpby][tmpbx]=='O') {
								done = false;
								break;
							}
							tmpbx += nx[i];
							tmpby += ny[i];
							Rchkmap[tmpry][tmprx][tmpby][tmpbx] = true;
						}
						else break;
					}
					else break;
				}
				if(tmpby==tmpry&&tmpbx==tmprx&&Map[tmpry][tmprx]!='O') {
					int tmpr = Math.abs(tmprx-rx) + Math.abs(tmpry-ry);
					int tmpb = Math.abs(tmpbx-bx) + Math.abs(tmpby-by);
					if(tmpr>tmpb){
						Rchkmap[tmpry][tmprx][tmpby][tmpbx]=false;
						tmprx -= nx[i];
						tmpry -= ny[i];
					}
					else{
						Rchkmap[tmpry][tmprx][tmpby][tmpbx] = false;
						tmpbx -= nx[i];
						tmpby -= ny[i];
					}
				}
				if(done == true) {
					if(cntinsert==true&&tmpcnt<cnt) {
						cnt = tmpcnt;
					}
					else if(cntinsert==false) {
						cnt = tmpcnt;
						cntinsert = true;
					}
					done = false;
					return;
				}
				else if(tmprx!=rx||tmpry!=ry||tmpbx!=bx||tmpby!=by){
					q.add(new Node(tmprx,tmpry,tmpbx,tmpby));
					FindWay(Rchkmap, tmpcnt);
				}
			}
		}
	}
}
class Node{
	int rx,ry,bx,by;
	public Node(int rx, int ry, int bx, int by) {
		this.rx = rx;
		this.ry = ry;
		this.bx = bx;
		this.by = by;
	}
};

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

문제

문제

출처

ICPC

반례나 틀린부분 찾아주시면 감사하겠습니다!! ㅠㅠ

sehlryn7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말