글 읽기 - 어디가 잘못되었는지 모르겠습니다..

ljs921026 5년 전 0

A의 최단거리를 찾은 후

경로를 표시한 다음

B의 최단거리를 찾고

둘을 더한 값과

이 과정을 거꾸로한 값(B먼저 구하고 A)

중 작은 값을 출력하도록 했습니다.

반례 혹은 잘못된 부분좀 알 수 있을까요?

import java.util.*;

public class Main {
	static Queue<Pair> q;
	static int n;
	static int m;
	static int[][] circuit;
	static int[][] check;
	static Pair A1;
	static Pair A2;
	static Pair B1;
	static Pair B2;
	static int[] dx= {1,-1,0,0};
	static int[] dy= {0,0,1,-1};
	static int max=987654321;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		circuit=new int[n+1][m+1];
		A1=new Pair(sc.nextInt(),sc.nextInt(),null,0);
		A2=new Pair(sc.nextInt(),sc.nextInt(),null,0);
		B1=new Pair(sc.nextInt(),sc.nextInt(),null,0);
		B2=new Pair(sc.nextInt(),sc.nextInt(),null,0);
		
		check=new int[n+1][m+1];
		int aFirst=bfs(A1,A2);
		int bSecond=bfs(B1,B2);
		int ans1;
		if(bSecond==-1)
			ans1=max;
		else
			ans1=aFirst+bSecond;
		
		check=new int[n+1][m+1];
		int bFirst=bfs(B1,B2);
		int aSecond=bfs(A1,A2);
		int ans2;
		if(aSecond==-1)
			ans2=max;
		else
			ans2=bFirst+aSecond;
		
		int res=Math.min(ans1, ans2);
		if(res>=max)
			System.out.println("IMPOSSIBLE");
		else
			System.out.println(res);
	}
	
	public static int bfs(Pair start,Pair end) {
		q=new LinkedList<Pair>();
		q.add(start);
		check[start.y][start.x]=1;
		
		while(!q.isEmpty()) {
			Pair p=q.remove();
			int y=p.y;
			int x=p.x;
			int cnt=p.cnt;
			
			if(y==end.y&&x==end.x) {
				check=new int[n+1][m+1];
				find(p);
				return cnt;
			}
			
			for(int i=0;i<4;i++) {
				int nextx=x+dx[i];
				int nexty=y+dy[i];
				if(0<=nexty&&nexty<=n&&0<=nextx&&nextx<=m&&check[nexty][nextx]==0) {
					q.add(new Pair(nexty,nextx,p,cnt+1));
					check[nexty][nextx]=1;
				}
			}
		}
		
		return -1;
	}
	
	public static void find(Pair start) {
		check[start.y][start.x]=1;
		Pair p=start;
		while(true) {
			p=p.pre;
			if(p==null)
				break;
			check[p.y][p.x]=1;
		}
	}
}

class Pair{
	Pair pre;
	int y;
	int x;
	int cnt;
	Pair(int y,int x,Pair pre,int cnt) {
		this.y=y;
		this.x=x;
		this.pre=pre;
		this.cnt=cnt;
	}
}

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

문제

문제

출처

ICPC

어디가 잘못되었는지 모르겠습니다..

ljs921026 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말