글 읽기 - 테스트케이스는 모두 맞는데 어디가 틀린지 모르겠습니다.

ih0070 5년 전 0

맵으로 실제 그려봐도 제 소스가 맞는거 같은데 도대체 무엇떄문에 틀린지 모르겠습니다.

반례를 알려주시면 감사하겠습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M, result;
	static int map[][];
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static Queue<Node> q = new LinkedList<>();

	public static void bfs() {

		while (!q.isEmpty()) {
			Node temp = q.poll();
			visited[temp.x][temp.y] = true;
			map[temp.x][temp.y] = temp.dist;

			for (int i = 0; i < 4; i++) {
				int x1 = temp.x + dx[i];
				int y1 = temp.y + dy[i];

				if (x1 < 0 || x1 >= N || y1 < 0 || y1 >= M) // 맵 범위 지정
					continue;
				if (map[x1][y1] == 0 && !visited[x1][y1]) { // 길이고 가본적 없다
					visited[x1][y1] = true;
					map[x1][y1] = temp.dist;
					q.add(new Node(x1, y1, temp.crash, temp.dist + 1));

				} else if (map[x1][y1] == 1 && !visited[x1][y1]) { // 벽이고 가본적 없다
					if (temp.crash == true) {
						visited[x1][y1] = true;
						map[x1][y1] = temp.dist;
						q.add(new Node(x1, y1, false, temp.dist + 1));
					}
				}
			}
		}
		result = map[N - 1][M - 1];
	}

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

		N = sc.nextInt();
		M = sc.nextInt();

		map = new int[N][M];
		visited = new boolean[N][M];

		String s;
		for (int i = 0; i < N; i++) {
			s = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}

		q.add(new Node(0, 0, true, 1));

		bfs();
		if (result == 0)
			result = -1;
		System.out.println(result);

/*		for (int i = 0; i < N; i++) {                 //맵에 그려보기
			for (int j = 0; j < M; j++) {
				System.out.printf("%2d ", map[i][j]);
			}
			System.out.println();
		}*/

	}

	public static class Node {
		int x;
		int y;
		boolean crash;
		int dist;

		public Node(int _x, int _y, boolean _crash, int _dist) {
			this.x = _x;
			this.y = _y;
			this.crash = _crash;
			this.dist = _dist;
		}
	}
}

djm03178 5년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

테스트케이스는 모두 맞는데 어디가 틀린지 모르겠습니다.

ih0070 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말