글 읽기 - ㅠㅠㅠ 왜틀렸다고 나올까요...

ccaa38 6년 전 0

bfs를이용하여 구현하였습니다.

visitInfo[][]행렬은 최단거리를 저장하는 행렬입니다.

ㅠㅠ 예제는 잘 실행이 되는데 왜 오류가 뜨는지 모르겠습니다.

아마 (100,100)일 경우에 시간이 너무 많이 걸려서 초과가 되었을 가능성이..있을 것 같은데ㅠㅠ

도와주세요..

#include <stdio.h>
#define		QUEUE_SIZE		500
#define		REPOSITION(position)	position%QUEUE_SIZE
#define		MAP_SIZE		101
#define		MAX_DATA		100000
//BFS 좌표
typedef struct _axis
{
	int row;
	int col;
}Axis;

//현재 좌표와 이전 좌표를 모두 저장
typedef struct _data
{
	Axis cur;
	Axis last;
}Data;
typedef struct _queue
{
	Data data[QUEUE_SIZE];
	int head;
	int rear;
	int data_num;
}Queue;

void QInit(Queue *q)
{
	q->data_num = 0;
	q->head = 0;
	q->rear = -1;
};

void QEnqueue(Queue *q, Data data)
{
	q->rear = REPOSITION(++q->rear);
	q->data[q->rear] = data;
	q->data_num++;
}

Data QDequeue(Queue *q)
{
	Data data;
	q->head = REPOSITION(q->head);
	q->data_num--;
	data = q->data[q->head++];
	return data;
}
void VInit(int v[][MAP_SIZE])
{
	int i, j;
	for (i = 0; i < MAP_SIZE; i++)
	{
		for (j = 0; j < MAP_SIZE; j++)
		{
			v[i][j] = MAX_DATA;
		}
	}
}
int main()
{
	int map[MAP_SIZE][MAP_SIZE];
	int visitInfo[MAP_SIZE][MAP_SIZE];
	int row,column,i,j;
	char ch[1000];
	Queue q;
	Axis cur = { 0,0 };
	Data pos = { cur ,{ 0,0 } };


	scanf("%d %d", &row, &column);
	
	for (i = 0; i < row; i++) {
		scanf("%s", ch);
		for (j = 0; j < column; j++) {
			map[i][j] = ch[j] - 48;
			//visit[i][j] = 0;
		}
	}

	VInit(visitInfo);
	QInit(&q);
	QEnqueue(&q, pos);
	visitInfo[cur.row][cur.col] = 1;

	while (q.data_num != 0)
	{
		if (map[cur.row + 1][cur.col] == 1 && cur.row + 1 < row)
		{
			Data addData = { {cur.row + 1,cur.col},cur };
			QEnqueue(&q, addData);
		}
		if (map[cur.row - 1][cur.col]==1 && cur.row - 1 >= 0)
		{
			Data addData = { { cur.row - 1,cur.col },cur };
			QEnqueue(&q, addData);
		}
		if (map[cur.row][cur.col + 1] ==1 && cur.col + 1 < column)
		{
			Data addData = { { cur.row,cur.col+1 },cur };
			QEnqueue(&q, addData);
		}
		if (map[cur.row][cur.col - 1] ==1 && cur.col - 1 >= 0)
		{
			Data addData = { { cur.row,cur.col -1 },cur };
			QEnqueue(&q, addData);
		}
		map[cur.row][cur.col] = 0;
		pos = QDequeue(&q);
		cur = pos.cur;
		if (visitInfo[cur.row][cur.col] > visitInfo[pos.last.row][pos.last.col] + 1) {
			visitInfo[cur.row][cur.col] = visitInfo[pos.last.row][pos.last.col] + 1;
		}
		if (cur.row == row - 1 && cur.col == column - 1)
		{
			printf("%d\n", visitInfo[cur.row][cur.col]);
			break;
		}
	}
}

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

문제

문제

출처

ICPC

ㅠㅠㅠ 왜틀렸다고 나올까요...

ccaa38 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말