글 읽기 - [C++] 1012 유기농 배추 문제 반례가 궁금합니다.

hwang0108 4년 전 0

예전 질문 글들 다 읽으면서 가로, 세로 확인 하였고 반례도 많이 넣어보았습니다.

그런데도 왜 저는 틀립니다가 나오는 걸까요 ㅠㅠ.

도와주십쇼 !!

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int T;
int M, N, k;
bool map[51][51];
bool visited[51][51];
int sum = 0;
vector <int> res;

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

	while (!q.empty()) {
		auto tmp = q.front();
		q.pop();
		int tmpi = tmp.first;
		int tmpj = tmp.second;

		for (int i = 0; i < 4; i++) {
			int ni = tmpi + di[i];
			int nj = tmpj + dj[i];

			if (ni < 0 || nj < 0 || ni >= N || nj >= M) {
				continue;
			}

			if (map[ni][nj] && !visited[ni][nj]) {
				q.push(make_pair(ni, nj));
				visited[ni][nj] = true;
			}
		}
	}
}


int main() {

	cin >> T;

	for (int i = 0; i < T; i++) {

		cin >> M >> N >> k;

		for (int j = 0; j < k; j++) {
			int x, y;
			cin >> x >> y;
			map[y][x] = true;
		}

		for (int a = 0; a < N; a++) {
			for (int b = 0; b < M; b++) {
				if (map[a][b] && !visited[a][b]) {
					bfs(a, b);
					sum++;
				}
			}
		}

		res.push_back(sum);
		sum = 0;
	}

	for (int i = 0; i < T; i++) {
		cout << res[i] << endl;
	}
}

djm03178 4년 전 0

매 케이스마다 초기화를 해야 한다는 답변이 아마도 수도 없이 많을 거라고 생각됩니다.

hwang0108 4년 전 0

죄송합니다 ㅠㅠ 무슨 말씀인지 잘 모르겠어서 그런데, 저가 케이스마다 초기화를 안해주었다는 뜻인가요??

djm03178 4년 전 0

그렇습니다. map이나 visited 등에 이전 케이스에서 사용한 내용이 그대로 남아있습니다.

간단히 아래와 같은 예시만으로도 틀립니다.

hwang0108 4년 전 0

와 정말정말 감사합니다 !!

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

문제

문제

출처

ICPC

[C++] 1012 유기농 배추 문제 반례가 궁금합니다.

hwang0108 4년 전 0

djm03178 4년 전 0

hwang0108 4년 전 0

djm03178 4년 전 0

hwang0108 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말