글 읽기 - 시간초과는 해결했는데 이젠 어떤 예외가 있는지 모르겠습니다 ㅠ.ㅠ(주석첨부)

dreammusic23 7년 전 0

정말 몇일째 고생하고 있는건지 모르겠습니다 ㅠ.ㅠ...

일단 탈출 할 수 있을 경우에 그 값을 리턴하도록 했습니다!

테스트케이스도 맞고, 시작부터 탈출된 경우도 추가해놨는데 틀렸다고 뜹니다...

도대체 무슨 케이스가...!?

#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> xy;
typedef pair<int,xy> typeXY;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool escape(int w,int h,int x,int y){
	if(x==0||x==w-1)
		return true;
	if(y==0||y==h-1)
		return true;
	return false;
}
int bfs(int w,int h,int sx,int sy,char map[][1001]){
	// queue 선언
	// typeXY의 int부분은 1,2로 구분됨
	// 1인 경우는 상근이의 이동
	// 2인 경우는 불의 이동
	queue<typeXY> q;
	// check배열 선언
	// 값은 -1 또는 자연수임
	// -1인 경우는 불이 타오를 경우
	// 자연수는 상근이가 이동한 초
	int check[1001][1001]={0};
	// 초기값 큐에 넣고 체크해줌
	q.push(typeXY(1,xy(sx,sy)));
	check[sx][sy]=1;
	//불의 위치를 찾아서 큐에 넣어줌
	for(int i=0;i<w;i++){
		for(int j=0;j<h;j++){
			if(map[i][j]=='*'){
				q.push(typeXY(2,xy(i,j)));
			}
		}
	}
	while(!q.empty()){
		// num = typeXY의 int값 (1 or 2)
		// x,y는 큐에 들어있던 좌표
		int num=q.front().first,x=q.front().second.first,y=q.front().second.second;
		q.pop();
		for(int i=0;i<4;i++){
			// 상하좌우에 대해서
			int xx=x+dir[i][0],yy=y+dir[i][1];
			// 맵을 벗어나면 제외
			if(xx<0||yy<0||xx>=w||yy>=h)
				continue;
			// 현재 좌표가 벽에 막혀있으면 제외
			if(map[xx][yy]=='#')
				continue;
			// 상근이일 경우
			if(num==1){
				//이미 방문한 경우 or 불이 있는 경우는 제외
				if(check[xx][yy])
					continue;
				q.push(typeXY(1,xy(xx,yy)));
				check[xx][yy]=check[x][y]+1;
				//탈출했는지 확인
				if(escape(w,h,xx,yy))
					return check[xx][yy];
			}
			// 불일 경우
			if(num==2){
				if(check[xx][yy]==-1)
					continue;
				q.push(typeXY(2,xy(xx,yy)));
				check[xx][yy]=-1;
			}
		}
	}
	// 탈출 실패
	return -1;
}
int main(){
	int t;
	for(scanf("%d",&t);t--;){
		int w,h;
		int sx,sy;
		char map[1001][1001]={0};
		scanf("%d%d",&h,&w);
		for(int i=0;i<w;i++){
			scanf("%s",map[i]);
			for(int j=0;j<h;j++){
				// 상근이의 시작위치 찾기
				if(map[i][j]=='@')
					sx=i,sy=j;
			}
		}
		//이미 탈출한 경우인지 확인
		if(escape(w,h,sx,sy)){
			printf("1\n");
			continue;
		}
		// bfs
		int ans=bfs(w,h,sx,sy,map);
		if(ans>0)
			printf("%d\n",ans);
		else
			printf("IMPOSSIBLE\n");
	}
	return 0;
}

yukariko 7년 전 1

처음 불들을 넣을때 체크가 안되어있는것 같네요

ntopia 7년 전 1

큐에 넣을 때 불을 먼저 넣고 사람을 나중에 넣어야 제대로 돌아갈 것 같습니다

예를 들어 아래와 같은 데이터는 현재 코드로는 잘못된 값이 나올 것 같네요

###

#@.

##*

dreammusic23 7년 전 0

해결했습니다! 감사합니다~~ ㅠㅠ

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

문제

문제

출처

ICPC

시간초과는 해결했는데 이젠 어떤 예외가 있는지 모르겠습니다 ㅠ.ㅠ(주석첨부)

dreammusic23 7년 전 0

yukariko 7년 전 1

ntopia 7년 전 1

dreammusic23 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말