글 읽기 - 런타임이 나는 오류가 무엇일까요 ..?

kimminsu6110 7년 전 0

제가 생각한 알고리즘은 .

먼저 0의 위치를 탐색한다음 '.' 로바꿔주고 스타트큐에 넣어주는 것입니다.

스타트큐에 넣어준 데이터를 다시 다른 bfs로 돌려서 1에 도착할 수 있는지를 확인하고 , 열쇠를 만났을 시 그당시에 데이터를 스타트큐에 넣어줍니다.

그리고 bfs를 빠져나와서 다시 그 스타트큐를 넣어줘서 순차적으로 1에 도달할수 있는 지를 확인합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int r = 0;
int c= 0;
int visit[100][100];
char arr[100][100];
int curKey[100][255];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int aQue = 0;
int bQue = 0;
int minRsult = 1000;
int flag = 0;


int QueX[10000];
int QueY[10000];
int QueL[10000];
int sQueX[100];
int sQueY[100];
int sQueL[100];
void init();
void push(int a, int b, int c);
void spush(int a, int b, int c, int count, char key);
void Input();
void Bfs(int cnt);

int main()
{
	int i = 0;
	Input();
	while (i < bQue)
	{
		Bfs(i);
		if (flag == 1)
		{
			return 0;
		}
		init();
		i++;
	}
	printf("-1\n");
	return 0;
}

void push(int a,int b,int c)
{
	QueX[aQue] = a;
	QueY[aQue] = b;
	QueL[aQue] = c;
	aQue++;
}
void spush(int a, int b, int c, int count, char key)
{
	sQueX[bQue] = a;
	sQueY[bQue] = b;
	sQueL[bQue] = c;
	if (bQue != 0)
	{
		memcpy(curKey[bQue], curKey[count], sizeof(curKey[bQue]));
	}
	if (key != 0)
	{
		curKey[bQue][key - 32] = 1;
	}
	bQue++;
}

void Input()
{
	int i = 0;
	int k = 0;
	scanf("%d %d", &r, &c);
	for (i = 0; i < r; i++)
	{
		scanf("%s", arr[i]);
	}
	for (i = 0; i < r; i++)
	{
		for (k = 0; k < c; k++)
		{
			if (arr[i][k] == '0')
			{
				visit[i][k] = 1;
				arr[i][k] = '.';
				spush(i, k, 0, 0, 0);
			}
		}
	}

}

void Bfs(int cnt)
{
	int i = 0;
	int rx = 0;
	int ry = 0;
	int count = 0;
	push(sQueX[cnt], sQueY[cnt], sQueL[cnt]);
	visit[sQueX[cnt]][sQueY[cnt]] = 1;
	while (count < aQue)
	{
		if (arr[QueX[count]][QueY[count]] == '1')
		{
			if (minRsult > QueL[count])
			{
				minRsult = QueL[count];
				flag = 1;
				printf("%d\n", minRsult);
				//return;
			}
		}
		for (i = 0; i < 4; i++)
		{
			rx = QueX[count] + dx[i];
			ry = QueY[count] + dy[i];
			if (rx<r && ry <c && rx>-1 && ry >-1 && visit[rx][ry] == 0)
			{
				if (arr[rx][ry] != '#')
				{
					if (arr[rx][ry] == '.' || arr[rx][ry] == '1')
					{
						visit[rx][ry] = 1;
						push(rx, ry, QueL[count] + 1);
					}
					else if (arr[rx][ry] >= 'a' && arr[rx][ry] <= 'f')
					{
						if (curKey[cnt][arr[rx][ry] - 32] != 1)
						{
							spush(rx, ry, QueL[count] + 1, cnt, arr[rx][ry]);
							visit[rx][ry] = 1;
						}
						else
						{
							visit[rx][ry] = 1;
							push(rx, ry, QueL[count] + 1);
						}

					}
					else if (arr[rx][ry] >= 'A'&& arr[rx][ry] <= 'F')
					{
						if (curKey[cnt][arr[rx][ry]] == 1)
						{
							visit[rx][ry] = 1;
							push(rx, ry, QueL[count] + 1);
						}
						else
						{

						}
					}
				}
			}

		}
		count++;

	}

}

void init()
{

	memset(visit, 0, sizeof(visit));
	memset(QueX, 0, sizeof(QueX));
	memset(QueY, 0, sizeof(QueY));
	memset(QueL, 0, sizeof(QueL));
	aQue = 0;
}

	

choko100 2년 전 0

안녕하세요, 런타임 에러는 큐 사이즈 때문에 난 것 같습니다.

최대 6종류의 열쇠를 다 먹고 모든 가능한 지점을 다 돌아다니는 경우 50 x 50 x (2^6) 이 되어서 16만이 됩니다.

16만 넘게 curKey, minRsult, Que 와 sQue 사이즈를 조정해주시면 될 것 같습니다.

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

문제

문제

출처

ICPC

런타임이 나는 오류가 무엇일까요 ..?

kimminsu6110 7년 전 0

choko100 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말