글 읽기 - 72%에서 막히는데 반례 찾는것 좀 부탁드립니다.

tadei 6년 전 2

며칠동안 생각해봤는데 도저히 못찾겠습니다.

여러 케이스로 테스트 했고 다른 질문도 찾아봤는데 원인을 알수가 없네요

180도 회전은 2, 90도 회전은 1 로 설정했고 벽 뚫고 전진못하게 해놨습니다.

아마도 사소한 실수를 하지 않았나 싶은데 반례 찾는것 좀 부탁드립니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main {
	static int[] dy = { 0, 0, 1, -1 };
	static int[] dx = { 1, -1, 0, 0 };

	public static void main(String args[]) throws Exception {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int m = scan.nextInt();

		int[][] array = new int[n][m];
		int[][][] dp = new int[n][m][4];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				array[i][j] = scan.nextInt();
			}
		}

		// 동쪽이 0, 서쪽이 1, 남쪽이 2, 북쪽이 3

		ArrayList<Spot> list = new ArrayList<>();
		list.add(new Spot(scan.nextInt() - 1, scan.nextInt() - 1, scan.nextInt() - 1, 0));
		Spot end = new Spot(scan.nextInt() - 1, scan.nextInt() - 1, scan.nextInt() - 1, 0);

		while (list.size() > 0) {
			Spot temp = list.get(0);

			if (dp[temp.y][temp.x][temp.direction] == 0 || dp[temp.y][temp.x][temp.direction] > temp.count) {

				for (int i = 0; i < 4; i++) {
					int rotate = Rotate(temp.direction, i);

					if (dp[temp.y][temp.x][i] == 0 || dp[temp.y][temp.x][i] > temp.count + rotate) {
						dp[temp.y][temp.x][i] = temp.count + rotate;

						for (int j = 1; j <= 3; j++) {
							int ny = temp.y + j * dy[i];
							int nx = temp.x + j * dx[i];

							if (ny < 0 || nx < 0 || ny >= array.length || nx >= array[0].length || array[ny][nx] == 1)
								break;

							if (dp[ny][nx][i] == 0 || dp[ny][nx][i] > temp.count + rotate + 1) {
								list.add(new Spot(ny, nx, i, temp.count + rotate + 1));
							}
						}
					}
				}
			}
			list.remove(0);
		}
		System.out.println(dp[end.y][end.x][end.direction]);
	}

	public static int Rotate(int dir1, int dir2) {
		if (dir1 == dir2)
			return 0;
		else if (dir1 == 0 || dir1 == 1) {
			if (dir2 == 2 || dir2 == 3) {
				return 1;
			} else
				return 2;
		} else {
			if (dir2 == 0 || dir2 == 1) {
				return 1;
			} else
				return 2;
		}
	}

	public static class Spot {
		int y, x, direction, count;

		public Spot(int y, int x, int direction, int count) {
			super();
			this.y = y;
			this.x = x;
			this.direction = direction;
			this.count = count;
		}
	}
}

rlatjrdnjs 6년 전 2

출발점과 도착점...

여기까지만 말씀드릴게요

tadei 6년 전 5

감사합니다 덕분에 해결했네요

출발점과 도착점의 위치와 방향이 모두 같을 때가 문제였습니다

72%에서 막히시면 참고하시길

skynet 5년 전 0

간사합니다!

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

문제

문제

출처

ICPC

72%에서 막히는데 반례 찾는것 좀 부탁드립니다.

tadei 6년 전 2

rlatjrdnjs 6년 전 2

tadei 6년 전 5

skynet 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말