글 읽기 - 틀렸습니다 ㅠㅠㅠㅠ 반례가 있을까요?

hyesoo13 4년 전 0

예제도 다 잘 나오고 다른 질문글에 있는 반례도 잘 나옵니다... 어디서 틀린건지 아무리 찾아봐도 모르겠어서 질문 올립니다. 반례주시면 정말 감사합니다!!

#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;

#define ABS(a) (((a) > 0) ? (a) : -(a))

int arr[52][52];

int check[52][52];
int checknum; 

int dir[2][4] = { {-1,0,1,0}, {0,1,0,-1} };

int temp;
int n, l, r;

int total;

vector<pair<int, int>> v;//v에 들어있는 애들은 국경선이 열린 애들


/*
국경선이 열리는 국가들을 v에 넣고
total(연합의 인구수)를 구함
*/
void dfs(int x, int y) 
{
	if (check[x][y] <= checknum) //작은때는 이미 한번 다른 국가들끼리의 인구이동을 한 경우, 같을때는 현재 국가와 이미 연결되어 있을 경우
		return;
	check[x][y] = checknum;
	v.push_back({ x,y });
	total += arr[x][y];
	for (int i = 0; i < 4; i++)
	{
		temp = ABS(arr[x + dir[0][i]][y + dir[1][i]] - arr[x][y]);
		if (temp >= l && temp <= r)
			dfs(x + dir[0][i], y + dir[1][i]);
	}
}

int main()
{
	int result;
	scanf("%d %d %d", &n, &l, &r);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &arr[i][j]);

	for (int j = 0; j <= n+1; j++)
		arr[j][0] = arr[j][n + 1] = arr[0][j] = arr[n + 1][j] = -1000;

	bool stop = false;
	int size;
	result = -1;
	while (stop == false)
	{
		result++;
		memset(check, 0, sizeof(int) * 2500);
		checknum = -5000;
		stop = true;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (check[i][j] > checknum)
				{
					dfs(i, j);
					checknum++;
					if (v.size() > 1)
					{
						stop = false;
						size = v.size();
						total /= size;
						for (int k = 0; k < size; k++)
							arr[v[k].first][v[k].second] = total;
					}
					total = 0;
					v.clear();
				}
			}
		}
	}
	printf("%d", result);
	return 0;
}

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

문제

문제

출처

ICPC

틀렸습니다 ㅠㅠㅠㅠ 반례가 있을까요?

hyesoo13 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말