글 읽기 - 시간초과 문제입니다!

rlagksrlf12 4년 전 0

시간초과 해결을 못하겠네요 ㅠ...

#include<stdio.h>
#include<queue>
#include<utility>
#include<vector>
#include<algorithm>
#include<ctype.h>
#include<memory.h>
#include <iostream>
#include<set>
#include<string>
#include<list>
using namespace std;
typedef struct
{
	int y, x;
}pt;
int n;
int arr[21][21];
int visited[21][21];
int bsc = 0;
int bs = 2;
int sy, sx;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
int ans = 0;
vector<pair<int,int>> eat;
queue<pt> q;
void cq(queue<pt> &q)
{
	queue<pt> empty;
	swap(empty, q);
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.first == b.first)
	{
		return a.second < b.second;
	}
	else
	{
		return a.first < b.first;
	}
}
int check()
{
	int flag = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j]!=0&&arr[i][j] < bs) flag = 1;
		}
	}
	return flag;
}
void bfs(int y, int x)
{
	pt tmp;
	visited[y][x] = 1;
	tmp.y = y;
	tmp.x = x;
	q.push(tmp);
	int s = 0;
	while (!q.empty())
	{
		pt t=q.front();
		q.pop();
		if (s == visited[t.y][t.x]) return;

		for (int i = 0; i < 4; i++)
		{
			int ny = t.y + dy[i];
			int nx = t.x + dx[i];
			if (ny < n&&ny >= 0 && nx < n&&nx>=0)
			{
				if (visited[ny][nx] == 0)
				{
					if (arr[ny][nx] >=1 &&arr[ny][nx]<=6&&arr[ny][nx] < bs)
					{
						pt tt;
						visited[ny][nx] = visited[t.y][t.x] + 1;//아직먹으면안됨
						s = visited[ny][nx];
						eat.push_back(make_pair(ny,nx));
						tt.y = ny;
						tt.x = nx;
						q.push(tt);
					}
					else if (arr[ny][nx] == bs||arr[ny][nx]==0)
					{
						pt tt;
						visited[ny][nx] = visited[t.y][t.x] + 1;
						tt.y = ny;
						tt.x = nx;
						q.push(tt);
					}
				}
			}
		}
	}

}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 9)
			{
				sy = i;
				sx = j;
				arr[i][j] = 0;
			}
		}
	}
	while (check())
	{
		memset(visited, 0, sizeof(visited));
		eat.clear();
		cq(q);
		bfs(sy, sx);
		if (eat.size() != 0)
		{
			sort(eat.begin(), eat.end());
			bsc++;
			if (bsc == bs)
			{
				bsc = 0;
				bs++;
			}
			int yy = eat[0].first;
			int xx = eat[0].second;
			arr[yy][xx] = 0;
			sy = yy;
			sx = xx;
			ans += visited[yy][xx] - 1;
		}
	}
	printf("%d", ans);
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 문제입니다!

rlagksrlf12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말