글 읽기 - 뭐가 문제일까요 ㅎㅎ...

kokoxg2 7년 전 0

다 되는데 뭐가 문제일까요.. ㅎㅎ

#include <cstdio>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

const int MAX = 51;
short farm[MAX][MAX];			// 농장 배열
vector< pair<int, int> > vec;	// 군집 지역 시작지점
queue< pair<int, int> > tmp;	// bfs할 때 사용할 녀석

int dx[4] = { -1, 1, 0, 0 };	// 상하
int dy[4] = { 0, 0, -1, 1 };	// 좌우

int main() {
	
	int t, i, j, n, m, k, x, y, cnt = 0, l; // cnt : 군집지역의 수
											// k : 배추의 수 ( 나중에 배추의 수가 0이면 바로 while문 종료 )
	scanf("%d", &t);

	for (i = 0; i < t; ++i) {

		scanf("%d %d %d", &m, &n, &k);  

		for (j = 0; j < k; ++j) { // 배추 입력

			scanf("%d %d", &y, &x);
			vec.push_back(make_pair(x, y));
			farm[x][y] = 1; 
		}

		while (!vec.empty()) {

			pair<int, int> p = vec.back(); // 군집 지역의 시작점
			vec.pop_back();
			
			if (farm[p.first][p.second] != 0) {	// 배추가 없으면 pass !

				tmp.push(p); // 출발지점 입력

				while (!tmp.empty()) { // 배추 탐색을 다 끝내면 종료

					x = tmp.front().first;  // 배추 X 좌표
					y = tmp.front().second; // 배추 Y 좌표
					farm[p.first][p.second] = 0; // 배추 없애기
					tmp.pop(); // 다 쓴 지역 빼기

					for (l = 0; l < 4; ++l) { 

						int nx = x + dx[l];  // 상하 좌표 계산
						int ny = y + dy[l];  // 좌우 좌표 계산

						if (nx < 0 || n <= nx || ny < 0 || m <= ny) continue; // 범위를 넘어가면 PASS

						if (farm[nx][ny] == 1) { // 배추가 있는 지역이면
							farm[nx][ny] = 0;	// 배추를 get !하고
							tmp.push(make_pair(nx, ny)); // 해당 지역을 다시 출발점으로 !
							k--; // 배추 수 - 1
						}													
					}
				}
				cnt++; // 군집지역 + 1
			}

			if (k == 0) // 배추가 하나도 없으면 Pass!
				break;
		}
		
		vec.clear(); // 벡터 초기화
		printf("%d\n", cnt); // 출력
		cnt = 0; // 군집지역 초기화
	}
	return 0;
}

kokoxg2 7년 전 0

아 배열초기화.................................................

#include <cstdio>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

const int MAX = 51;
short farm[MAX][MAX];			// 농장 배열
vector< pair<int, int> > vec;	// 군집 지역 시작지점
queue< pair<int, int> > tmp;	// bfs할 때 사용할 녀석

int dx[4] = { -1, 1, 0, 0 };	// 상하
int dy[4] = { 0, 0, -1, 1 };	// 좌우

int main() {
	
	int t, i, j, n, m, k, x, y, cnt = 0, l; // cnt : 군집지역의 수
											// k : 배추의 수 ( 나중에 배추의 수가 0이면 바로 while문 종료 )
	scanf("%d", &t);

	for (i = 0; i < t; ++i) {

		scanf("%d %d %d", &m, &n, &k);  

		for (j = 0; j < k; ++j) { // 배추 입력

			scanf("%d %d", &y, &x);
			vec.push_back(make_pair(x, y));
			farm[x][y] = 1; 
		}

		while (!vec.empty()) {

			pair<int, int> p = vec.back(); // 군집 지역의 시작점
			vec.pop_back();
			
			if (farm[p.first][p.second] != 0) {	// 배추가 없으면 pass !

				tmp.push(p); // 출발지점 입력

				while (!tmp.empty()) { // 배추 탐색을 다 끝내면 종료

					x = tmp.front().first;  // 배추 X 좌표
					y = tmp.front().second; // 배추 Y 좌표
					farm[p.first][p.second] = 0; // 배추 없애기
					tmp.pop(); // 다 쓴 지역 빼기

					for (l = 0; l < 4; ++l) { 

						int nx = x + dx[l];  // 상하 좌표 계산
						int ny = y + dy[l];  // 좌우 좌표 계산

						if (nx < 0 || n <= nx || ny < 0 || m <= ny) continue; // 범위를 넘어가면 PASS

						if (farm[nx][ny] == 1) { // 배추가 있는 지역이면
							farm[nx][ny] = 0;	// 배추를 get !하고
							tmp.push(make_pair(nx, ny)); // 해당 지역을 다시 출발점으로 !
							k--; // 배추 수 - 1
						}													
					}
				}
				cnt++; // 군집지역 + 1
			}

			if (k == 0) // 배추가 하나도 없으면 Pass!
				break;
		}
		memset(farm, 0, sizeof(farm)); // 농장 초기화 ! 이거때문에 시간날림 ㅠㅠ ;
		vec.clear(); // 벡터 초기화
		printf("%d\n", cnt); // 출력
		cnt = 0; // 군집지역 초기화
	}
	return 0;
}

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

문제

문제

출처

ICPC

뭐가 문제일까요 ㅎㅎ...

kokoxg2 7년 전 0

kokoxg2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말