글 읽기 - 어디서 런타임 에러가 나는지 도저히 모르겠습니다 제발 살려주십쇼

juhongkim2 5년 전 0

이 소스의 어느부분에서 런타임 에러가 나는건가요?

10퍼쯤에서 런타임에러계속 뜨던데 진짜 미칠지경입니다...

제발 도와주십쇼...

혈압올라서 지금 뇌혈관 터지기 직전입니다...

#include <stdio.h>

typedef long long ll;

typedef struct pos{
	int xpos,ypos;
}Pos;

Pos q[1001*1001*2];
int N,check[1001][1001];
ll d[1001][1001];
char map[1001][1001];

int BFS(int x, int y)
{
	int i,tx,ty,f,r;
	int dx[4]={0,1,0,-1};
	int dy[4]={-1,0,1,0};
	Pos in,out;

	f=r=-1;
	in.xpos=x;
	in.ypos=y;
	q[++r]=in;

	while(f!=r){
		out=q[++f];
		check[out.ypos][out.xpos]=1;

		if(out.xpos==N-1 && out.ypos==N-1)
			return 1;

		for(i=0;i<4;i++){
			tx=out.xpos+dx[i];
			ty=out.ypos+dy[i];

			if(tx<0 || ty<0 || tx>=N || ty>=N)
				continue;
			if(check[ty][tx]==1)
				continue;
			if(map[ty][tx]=='#')
				continue;

			in.xpos=tx;
			in.ypos=ty;
			q[++r]=in;
		}
	}

	return 0;
}

int main()
{
	int i,j;

	scanf("%d",&N);

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			scanf(" %c", &map[i][j]);
		}
	}

	d[0][0]=1;
	for(i=1;i<N;i++){
		if(map[i][0]=='#')
			break;
		d[i][0]=1;
	}
	for(i=1;i<N;i++){
		if(map[0][i]=='#')
			break;
		d[0][i]=1;
	}
	for(i=1;i<N;i++){
		for(j=1;j<N;j++){
			if(map[i][j]=='#')
				d[i][j]=0;
			else{
				d[i][j]+=(d[i-1][j]+d[i][j-1]);
				d[i][j]%=2147483647;
			}
		}
	}

	if(d[N-1][N-1]==0){
		if(BFS(0,0)==1)
			printf("THE GAME IS A LIE\n");
		else
			printf("INCONCEIVABLE\n");
	}
	else
		printf("%lld\n",d[N-1][N-1]);
	return 0;
}

yukariko 5년 전 1

아래와 같이 고치니 정답을 받네요.

check를 큐에 넣을때마다 바로바로 해주지 않으면 방문처리가 제대로 되지 않아 중복된 좌표가 큐에 들어가게 됩니다.

#include <stdio.h>

typedef long long ll;

typedef struct pos{
	int xpos,ypos;
}Pos;

Pos q[1001*1001*2];
int N,check[1001][1001];
ll d[1001][1001];
char map[1001][1001];

int BFS(int x, int y)
{
	int i,tx,ty,f,r;
	int dx[4]={0,1,0,-1};
	int dy[4]={-1,0,1,0};
	Pos in,out;

	f=r=-1;
	in.xpos=x;
	in.ypos=y;
	q[++r]=in;

		check[y][x]=1;
	while(f!=r){
		out=q[++f];

		if(out.xpos==N-1 && out.ypos==N-1)
			return 1;

		for(i=0;i<4;i++){
			tx=out.xpos+dx[i];
			ty=out.ypos+dy[i];

			if(tx<0 || ty<0 || tx>=N || ty>=N)
				continue;
			if(check[ty][tx]==1)
				continue;
			if(map[ty][tx]=='#')
				continue;

		check[ty][tx]=1;
			in.xpos=tx;
			in.ypos=ty;
			q[++r]=in;
		}
	}

	return 0;
}

int main()
{
	int i,j;

	scanf("%d",&N);

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			scanf(" %c", &map[i][j]);
		}
	}

	d[0][0]=1;
	for(i=1;i<N;i++){
		if(map[i][0]=='#')
			break;
		d[i][0]=1;
	}
	for(i=1;i<N;i++){
		if(map[0][i]=='#')
			break;
		d[0][i]=1;
	}
	for(i=1;i<N;i++){
		for(j=1;j<N;j++){
			if(map[i][j]=='#')
				d[i][j]=0;
			else{
				d[i][j]+=(d[i-1][j]+d[i][j-1]);
				d[i][j]%=2147483647;
			}
		}
	}

	if(d[N-1][N-1]==0){
		if(BFS(0,0)==1)
			printf("THE GAME IS A LIE\n");
		else
			printf("INCONCEIVABLE\n");
	}
	else
		printf("%lld\n",d[N-1][N-1]);
	return 0;
}

juhongkim2 5년 전 0

소름돋습니다 진짜...

여태까지 방문할때마다 체크쓰는 방식을 썼는데 최근들어 빼줄때 체크하는 방식으로 바꿔썼었는데...

진짜 이런 사소한거 하나하나를 꼼꼼하게 공부해야함을 또다시 깨닫고 갑니다...

진짜 감사합니다ㅠㅠ 덕분에 잠 잘수 있겠네요....

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

문제

문제

출처

ICPC

어디서 런타임 에러가 나는지 도저히 모르겠습니다 제발 살려주십쇼

juhongkim2 5년 전 0

yukariko 5년 전 1

juhongkim2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말