글 읽기 - 아기상어 시간초과 ㅠㅠ

wltn0630 5년 전 0

예제는 다 맞는데... 시간초과가 납니다 채점시 ㅠ 어디서 줄여야할지를 모르겠어요.. 알려주시면 감사합니다 ㅠ

#include <stdio.h>
#pragma warning(disable : 4996)
#define MAX 100*100*100

typedef struct {
	int x;
	int y;
}Queue;

Queue queue[MAX];
int wp, rp;

int map[20 + 5][20 + 5];
int check[20 + 5][20 + 5];
int visit[20 + 5][20 + 5];

int tbl[20 + 5][20 + 5];

int N;
int time;
int scale = 2;

int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

int enqueue(int x, int y)
{
	if (wp == MAX) return 0;

	queue[wp].x = x;
	queue[wp++].y = y;
	return 1;
}

int dequeue(Queue *q)
{
	if (rp == wp) return 0;

	*q = queue[rp++];
	return 1;
}

int eatable(void)
{
	int cnt = 0;
	for(int i = 0 ; i < N ; i++)
		for (int j = 0; j < N; j++)
		{
			cnt = 0;
			if (map[i][j])
			{
				if (map[i][j] < scale)
				{
					for (int d = 0; d < 4; d++)
					{
						int x = i + dx[d], y = j+dy[i];
						if ((x < 0 || x >= N || y < 0 || y >= N) || map[x][y] > scale) cnt++;
					}
					if (cnt < 4)
						return 1;
					
				}
			}
		}
	return 0;
}

void bfs(int x, int y)
{
	Queue q;
	int flag = 0;
	int cnt = 0;

	int tmpx= x, tmpy = y;
	map[x][y] = 0;
	tbl[x][y] = 0;

	while (eatable())
	{
		int tt;
		int tx = -1, ty = -1;
		wp = rp = 0;
		enqueue(tmpx, tmpy);
		flag = 0;
		
		while (dequeue(&q))
		{
			if (flag) break;
			for (int i = 0; i < 4; i++)
			{
				int xx = q.x + dx[i];
				int yy = q.y + dy[i];
				if (xx < 0 || xx >= N || yy < 0 || yy >= N) continue;

				if (map[xx][yy] > scale) continue;
				if (map[xx][yy] == scale)
				{
					if (!check[xx][yy])
					{
						visit[xx][yy] = visit[q.x][q.y] + 1;
						check[xx][yy] = 1;
						enqueue(xx, yy);
					}
				}
				if (!map[xx][yy] && !check[xx][yy])
				{
					visit[xx][yy] = visit[q.x][q.y] + 1;
					check[xx][yy] = 1;
					enqueue(xx, yy);
				}
				if(map[xx][yy] && map[xx][yy] < scale) // 일단 먹잇감 찾았을 때 위->왼순으로 비교해야함.
				{
					if (tx == -1 && ty == -1)
					{
						tt = visit[q.x][q.y] + 1;
						tx = xx, ty = yy;
					}
					else
					{
						if (tt < visit[q.x][q.y] + 1)
						{
							flag = 1;
							break;
						}
						if (tx < xx) continue;
						if (tx == xx && ty < yy) continue;

						tx = xx, ty = yy;
					}
				}
			}
		}
		map[tx][ty] = 0;
		time = tt;
		cnt++;
		if (scale == cnt)
		{
			scale++;
			cnt = 0;
		}

		tmpx = tx, tmpy = ty;
		memset(check, 0, sizeof check);

		check[tx][ty] = 1;
		visit[tx][ty] = time;
		tbl[tx][ty] = time;
	}
}

int main(void)
{
	int sx, sy;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9)
			{
				check[i][j] = 1;
				sx = i, sy = j;
			}
		}

	bfs(sx,sy);

	printf("%d", time);

	return 0;
}

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

문제

문제

출처

ICPC

아기상어 시간초과 ㅠㅠ

wltn0630 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말