글 읽기 - 질문에서의 반례를 풀었는데 왜 안되는지?

ohst76 2년 전 0

정말 모르겠습니다.

여러가지 해봤는데 안되네요.ㅜㅜㅜ

#include <stdio.h>															
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 105

int map[MAX][MAX];
int visited[MAX][MAX];
int position[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
int target_x[MAX];
int target_y[MAX];
int result[MAX];
int in_cnt;
int M, N, K;
int total_counter;
int counter;

void bfs(int x, int y)
{
	queue<pair<int, int>>q;
	q.push({ x, y });
	visited[x][y] = 0;

	total_counter++;
	counter++;

	int i, j;
	int dx, dy, dq, dw;
	while (q.size())
	{
		dx = q.front().first;
		dy = q.front().second;
		q.pop();

		for (i = 0; i < 4; i++)
		{
			dq = dx + position[i][0];
			dw = dy + position[i][1];

			if ((dq < 0) || (dw < 0) || (dq >= M) || (dw >= N) || (map[dq][dw] == 1))
			{
				continue;
			}
			if (visited[dq][dw] && map[dq][dw] == 0)
			{
				counter++;
				visited[dq][dw] = 0;
				q.push({ dq, dw });
			}
		}
	}

}

void draw()
{	
	int i, j, t;	
	int st = 2;

	for (t = 0; t < K + 2; t+=2)
	{				
		for (i = target_x[t]; i < target_x[t + 1]; i++)
		{
			for (j = target_y[t]; j < target_y[t + 1]; j++)
			{
				map[j][i] = 1;
			}
		}		
	}
}

int main()
{
	scanf("%d %d %d", &M, &N, &K);

	int i, j;
	int st1, st2, st3, st4;

	for (i = 0; i < K; i++)
	{
		scanf("%d %d %d %d", &st1, &st2, &st3, &st4);
		target_x[in_cnt] = st1;
		target_y[in_cnt] = st2;
		in_cnt++;
		target_x[in_cnt] = st3;
		target_y[in_cnt] = st4;
		in_cnt++;
	}
	
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			visited[i][j] = 1;
		}
	}

	draw();

	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (visited[i][j] && map[i][j] != 1)
			{
				bfs(i, j);
				result[total_counter] = counter;
				counter = 0;
			}
		}
	}

	printf("%d\n", total_counter);


	sort(result, result + total_counter + 1);

	for (i = 1; i <= total_counter; i++)
	{
		printf("%d ", result[i]);
		result[i] = 0;
	}
	total_counter = 0;
	in_cnt = 0;
	return 0;
	}

kdh6429 2년 전 0

62번쨰 줄의 t++ 와 71 번째 줄 t+=1 이 어떤 의미인가요?

ohst76 2년 전 0

71번째의 t + 1 은 도형의 첫번째 x 값과 두번째 x 값 배열에 저장된 값을 2개씩 띄우기 위해서 그렇게 한것이고,

62번째 t++은 한개씩 증가 하게 된것 인데, 말씀하신 부분으로 두개다 합쳐서 할수 있을것 같습니다.

그런데 그걸 수정해도 문제의 안되는 부분은 동일하네요.

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

문제

문제

출처

ICPC

질문에서의 반례를 풀었는데 왜 안되는지?

ohst76 2년 전 0

kdh6429 2년 전 0

ohst76 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말