글 읽기 - 반례가 무엇일까요? ㅜㅜ

skr1995 4년 전 0

예제는 되는데 반례가 궁금합니다 ㅜㅜ

import java.util.*;


public class Main {
	
	static int n,m;
	
	static int[] dx= {-1,0,1,0},dy= {0,-1,0,1};
	static int[][] arr;
	static int[][] visit; //$$
	static Queue<Pos>q=new LinkedList<Pos>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		arr=new int[n+1][m+1];
		for (int i = 1; i <= n; i++) {
			String temp=sc.next();
			for (int j =1; j <= m; j++) {
				arr[i][j]=temp.charAt(j-1)-'0';
			}
		}
		//........................
		visit=new int[n+1][m+1];
		for (int i = 0; i < visit.length; i++) {
			Arrays.fill(visit[i],Integer.MAX_VALUE);
		}
		bfs();
	}
	static void bfs() {
		q.offer(new Pos(1,1,1));
		visit[1][1]=1;
		while(!q.isEmpty()) {
			Pos now=q.poll();
//			System.out.println(String.format("%d %d %d",now.x,now.y,now.dis));
			
			for (int i = 0; i < 4; i++) {
				int nx=dx[i]+now.x;
				int ny=dy[i]+now.y;
				
				if(nx<=0 || ny<=0 || nx>n || ny>m)continue;
				if(visit[nx][ny]<=now.dis+1)continue;
				if(arr[nx][ny]==0) {
					visit[nx][ny]=now.dis+1; //벽을 깨면 1을 더해지기 때문
					q.offer(new Pos(nx,ny,now.dis+1,now.busum));
				}
				else if(now.busum==false) { //arr[nx][ny]==1일때  // 아직 안 부쉈으면 
					visit[nx][ny]=now.dis+1; //벽을 깨면 1을 더해지기 때문
					q.offer(new Pos(nx,ny,now.dis+1,true)); 
				}
			}
		}
		if(visit[n][m]==Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(visit[n][m]);
	}
	static class Pos{
		public boolean busum=false;
		public int x,y,dis;
		
		public Pos(int x, int y, int dis) {
			super();
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
		public Pos( int x, int y, int dis,boolean busum) {
			this.busum = busum;
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
	}
}

bakh1 4년 전 5

IN:

6 4
0000
1110
1000
0000
0111
0100

OUT:

(답): 9

(출력): -1

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

문제

문제

출처

ICPC

반례가 무엇일까요? ㅜㅜ

skr1995 4년 전 0

bakh1 4년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말