글 읽기 - 틀린 테스트케이스가 있을까요 ?

cocobino 5년 전 0

1) start 에서 시작해서 BFS를 돌린후

2) 현재 좌표와 다음좌표간의 방향이 다르면 dist[][] 배열에 +1 해주는 식으로 구현을 하였는데

몇가지 테스트케이스를 넣으면 맞는데... 틀리다구 떠서

뭔가 놓치고 있는거같아요 ㅜㅜ 고수님들 부탁드립니다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	 
	static int r,c; 
	static int map[][] = new int[101][101];
	
	
	static final int C =1;
	static final int wall = -1;
	static final int blank = 0;

	
	static int dx[] = {0,0,-1,1};//동서북남
	static int dy[] = {1,-1,0,0};
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		c = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		
		
		Node startc = new Node(-1,-1,-1);
		Node endc = new Node(-1,-1,-1);
		
		for(int i=0; i<r; i++) {
			String a = br.readLine();
			for(int j=0; j<c; j++) {
				switch(a.charAt(j)) {
				case 'C':
					map[i][j] = C;
					if(startc.x ==-1)startc = new Node(i,j,-1);
					else {
						endc = new Node(i,j,-1);
					}
					break;
				case '*':
					map[i][j] = wall;
					break;
				case '.':
					map[i][j] = blank;
					break;
				}
			}
		}// insert
		int dist[][]  = new int[r][c];
		for(int i=0; i<r; i++)Arrays.fill(dist[i], -1);
		
		dist[startc.x][startc.y] =0;//시작점을 0으로 만들어주기
		Queue<Node> q = new LinkedList<Node>();
		q.add(startc);
		
		while(!q.isEmpty()) {
			//startpoint 를 q에 넣음
			Node cur = q.poll();
			int dir = cur.dir;
			for(int i=0; i<4; i++) {
				int nx = cur.x +dx[i];
				int ny = cur.y + dy[i];
				int ndir =i;
				
				if(nx<0 || ny<0 ||nx>=r || ny >=c)continue;
				if(map[nx][ny]==wall)continue;
				// 1)다음칸이 이동가능하다면
				if(map[nx][ny] == C || map[nx][ny] == blank) {
					
				//2-1)같은방향으로 이동
					if(dir == ndir) {
						if(dist[nx][ny] == -1) {
						dist[nx][ny]=dist[cur.x][cur.y];
						q.add(new Node(nx,ny,i));
						}
						else if(dist[nx][ny] != -1) {
							if(dist[nx][ny]>dist[cur.x][cur.y]) {
								dist[nx][ny] = dist[cur.x][cur.y];
										q.add(new Node(nx,ny,i));
							}
						}
					}
				//2_2)다른방향으로 이동
					else if(dir != ndir) {
						if(dist[nx][ny]==-1) {
							dist[nx][ny] = dist[cur.x][cur.y]+1;
							q.add(new Node(nx,ny,i));
						}
						if(dist[nx][ny]>dist[cur.x][cur.y]+1) {
							dist[nx][ny] = dist[cur.x][cur.y]+1;
							q.add(new Node(nx,ny,i));
						}
					}

				}
			}
			
		}//while -end
			
		bw.write(String.valueOf(dist[endc.x][endc.y]-1));
		bw.flush();
		}// main -end
		
	
	}
	


class Node{
	int x,y,dir;
	public Node(int x, int y, int dir) {
		// TODO Auto-generated constructor stub
		this.x=x;
		this.y=y;
		this.dir=dir;
	}
}

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

문제

문제

출처

ICPC

틀린 테스트케이스가 있을까요 ?

cocobino 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말