글 읽기 - 틀렸습니다...

ljo950924 4년 전 0

제가 해본 모든 경우에서는 정답이 나오는데 제출 결과는 틀렸습니다가 나옵니다..

제가 실수로 DFS를 이용하여 풀었는데 그것 때문에 틀렸다고 나오는 건가요..?

아니면 어느 부분이 잘못된건지 혹은 어떤 반례가 있는지 좀 알려주세요ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int[][] mazz;
	static int[][] v;
	static int[][] d;
	static int[] di = {0, 1, 0, -1};
	static int[] dj = {1, 0, -1, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		mazz = new int[n][m];
		v = new int[n][m];
		d = new int[n][m];
		String tmp;
		for(int i=0; i<n; i++) {
			tmp = br.readLine();
			for(int j=0; j<m; j++) {
				mazz[i][j] = Integer.parseInt(tmp.charAt(j)+"");
			}
		}
		
		int count = findRoad(0,0);
		System.out.println(count);
	}

	static int findRoad(int i, int j) {
		if(i==n-1 && j==m-1) return 1;
		
		if(v[i][j]!=0) return d[i][j];
		v[i][j]=1;
		
		int ret=n*m+1;
		int ni, nj;
		for(int x=0; x<4; x++) {
			ni = i+di[x];
			nj = j+dj[x];
			
			if(ni>=0 && ni<n && nj>=0 && nj<m) {
				if(mazz[ni][nj]==1 && v[ni][nj] == 0) {
					ret = Math.min(ret, 1+findRoad(ni,nj));
				}
			}
		}
		return d[i][j] = ret;
	}
}

djm03178 4년 전 1

https://www.acmicpc.net/board/view/25832 4번을 보세요.

ljo950924 4년 전 0

감사합니다!! 저런게 있는 줄 몰랐네요;;

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

문제

문제

출처

ICPC

틀렸습니다...

ljo950924 4년 전 0

djm03178 4년 전 1

ljo950924 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말