글 읽기 - 어떤 틀린 케이스가 있을 지 궁금합니다.

ainch96 8년 전 0

bfs 정석을 사용 해서 정답을 구현했는데 어떤 부분에서 틀린 건지 잘 모르겠습니다. ㅠㅠㅠ

생각해 볼 수 있는 모든 케이스에서 답이 잘 나오는데 어떤 케이스에서 틀리게 나오는지 감이 잘 안옵니다.

#include <stdio.h>
#include <queue>
#define MAX(a,b) (a)>(b)?(a):(b)
using namespace std;

typedef pair < int, int > ii;
const int MAX = 510;
int picture[MAX][MAX];
queue < ii > q;

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

ii bfs(int n, int m){
	int num = 0;
	int size = 0;
	int tmp_size;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			if (picture[i][j] >= 0)continue;
			++num;
			tmp_size = 1;
			q.push(ii(i, j));
			picture[i][j] = num;

			while (!q.empty()){
				int now_r = q.front().first;
				int now_c = q.front().second;
				q.pop();

				for (int k = 0; k < 4;++k){
						int next_r = now_r + dx[k];
						int next_c = now_c + dy[k];
						if (next_r<1 || next_r>n)continue;
						if (next_c<1 || next_c>m)continue;
						if (picture[next_r][next_c] >= 0)continue;
						picture[next_r][next_c] = num;
						q.push(ii(next_r, next_c));
						++tmp_size;
					
				}
			}
			size = MAX(size, tmp_size);
		}
	}
	return ii(num, size);
}
int  main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for (int row = 1; row <= n; ++row){
		for (int col = 1; col <= m; ++col){
			int x;
			scanf("%d", &x);
			picture[row][col] = -1 * x;
		}
	}

	ii ans = bfs(n, m);
	printf("%d\n%d\n", ans.first, ans.second);
	return 0;
}

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

문제

문제

출처

ICPC

어떤 틀린 케이스가 있을 지 궁금합니다.

ainch96 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말