글 읽기 - 시간초과 질문입니다^^:

rbbinit 5년 전 0

시간초과를 해결하려고

일주일전에 푼것을 다시 해보았는데

똑같은 결과를 낳았습니다.

다만 문제는, 어느부분을 해결해야 시간초과를 해결할 수 있는지

모르겠습니다. 혹시 힌트 혹은 도움을 주실 수 있으신가요?

#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <functional>
#include <queue>
#include <stack>
using namespace std;

struct tomato {
	int x, y;
};

int zerocnt;
int idx;
tomato t[1001];
int M, N; //가로, 세로
const int dr[4] = { 1,0,-1,0 };
const int dc[4] = { 0,1,0,-1 };
int a[1001][1001];
//1익은토마토, 0안익음, -1 토마토x
queue <pair<int, int>> q;
int vis[1001][1001];
int dis[1001][1001];
int distemps[1001][1001];

void bfs(int depth)
{
	q.push({ t[depth].x, t[depth].y });
	vis[t[depth].x][t[depth].y]=1;

	while (!q.empty())
	{
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++)
		{
			int xx = tx + dr[i];
			int yy = ty + dc[i];

			if (xx < 0 || yy < 0 || xx >= M || yy >= N) continue;
			if (vis[xx][yy]) continue;
			if (a[xx][yy]==-1) continue;

			int tp = dis[xx][yy];
			//cout << xx << " " << yy << "\n";
			q.push({ xx, yy });
			vis[xx][yy] = 1;
			
			if(!a[xx][yy])
			a[xx][yy] = 9;
			
			dis[xx][yy] = dis[tx][ty] + 1;
			if (distemps[xx][yy] < dis[xx][yy])
				if (distemps[xx][yy] != 0)
					dis[xx][yy] = distemps[xx][yy];
			
			
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 1)
			{
				t[idx].x = i;
				t[idx].y = j;
				++idx;
			}
			if (a[i][j] == 0)
			{
				zerocnt++;
			}
		}
	}
	
	for (int ii = 0; ii <idx; ii++)
	{
		dis[t[ii].x][t[ii].y] = 0;
		bfs(ii);

		for (int j = 0; j < 1001; j++)
		{
			memset(vis[j], 0, sizeof(int) * 1001);
			memcpy(distemps[j], dis[j], sizeof(int) * 1000);
		}
				
	}
	int nicnt = 0; int tt = 0;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (a[i][j] == 9)
				++nicnt;
			if (dis[i][j] > tt)
				tt = dis[i][j];
			
		}
	}

	if (nicnt == zerocnt)
		cout << tt;
	else {
		cout << "-1";
	}
}

kyo20111 5년 전 1

1000 1000

1 0 1 0 1 . . .

0 0 0 0 0 . . .

1 0 1 0 1 . . .

0 0 0 0 0 . . .

. . . . . . . . .

이런 케이스에서 시간초과가 나지 않을까요?

1000*1000 크기의 배열을 250번 검사해봐야 합니다.

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

문제

문제

출처

ICPC

시간초과 질문입니다^^:

rbbinit 5년 전 0

kyo20111 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말