글 읽기 - 50%에서 틀렸다고 하는데...이유가 뭘까요?

dhedaa 7년 전 0

반례 케이스가 뭐가있죠....ㅠㅠ

//10216

#include <iostream>
#include <queue>

using namespace std;
int tc, n, x, y, r;
int map[5001][5001], visited[5001][5001];
queue<pair<int, int>> q;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void check()
{
	int team = 0;
	for (int i = 0; i < 5001; i++)
	{
		for (int j = 0; j < 5001; j++)
		{
			if (map[i][j] == 1)
			{			
				team++;
				map[i][j] = 0;
				q.push(make_pair(j, i));						
				while (!q.empty())
				{
					int a = q.front().first;
					int b = q.front().second;
					q.pop();
					for (int i = 0; i < 4; i++)//네방향으로 고고
					{
						int nx = a + dx[i];
						int ny = b + dy[i];
						if (nx > -1 && nx < 5001 && ny > -1 && ny < 5001 && map[ny][nx] == 1)
						{
							map[ny][nx] = 0;
							q.push(make_pair(nx, ny));							
						}
					}
				}				
			}				
		}
	}
	cout << team << endl;
}
void bfs(int r)
{	
	while (!q.empty())
	{
		int a = q.front().first;
		int b = q.front().second;			
		q.pop();		
		for (int i = 0; i < 4; i++)//네방향으로 고고
		{			
			int nx = a + dx[i];
			int ny = b + dy[i];
			if (nx > -1 && nx < 5001 && ny > -1 && ny < 5001 && map[ny][nx] == 0 && visited[b][a] <= r-1)
			{					
				map[ny][nx] = 1;
				q.push(make_pair(nx, ny));
				visited[ny][nx] = visited[b][a] + 1;
			}			
		}			
	}
}
int main()
{
	cin >> tc;	//testcase
	for (int j = 0; j < tc; j++)
	{
		cin >> n;	//number
		if (n > 3000) break;	
		for (int i = 0; i < n; i++)
		{
			cin >> x >> y >> r;	//x,y좌표 범위
			if (x > 5000 || y > 5000 || r > 5000) break;
			map[y][x] = 1;			
			q.push(make_pair(x, y));
			bfs(r);
		}
		check();		
	}	
}

rosedskim 6년 전 0

연결을 양방향으로 한번 해보고 돌려보세요 map체크할떄

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

문제

문제

출처

ICPC

50%에서 틀렸다고 하는데...이유가 뭘까요?

dhedaa 7년 전 0

rosedskim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말