글 읽기 - 반례를 알 수 있을까요?

xaemin 4년 전 0

예제 모두 통과되고 여기 게시판에 있는 반례들도 다 통과되는데.. 계속 실패라고 나옵니다 ㅜㅜ 도움 주실 수 있을까요?

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 650
int board[MAX][MAX];
int rowSize, colSize;
int curIsland=2;

typedef struct {
	int row, col;
} SCell;

int front=0, rear=0;
SCell queue[MAX];

bool IsEmpty() {
	if (front == rear)
		return true;
	else
		return false;
}

void Enqueue(int row, int col) {
	queue[rear].row = row;
	queue[rear].col = col;
	rear++;
	rear = rear % MAX;
}
SCell Dequeue() {
	if (!IsEmpty()) {
		front = (front + 1) % MAX;
		return queue[front-1];
	}
	else {
		SCell temp;
		temp.col = -1;
		temp.row = -1;
		return temp;
	}
}

void Flood(int row, int col) {
	int dcol[8] = { -1,-1,-1,0, 1, 1, 1, 0 };
	int drow[8] = { -1,0,1,1,   1, 0,-1, -1};	

	Enqueue(row, col);
	board[row][col] = curIsland;
	
	while (!IsEmpty()) {
		SCell temp = Dequeue();			
		for (int i = 0; i < 8; i++) {
			int r = temp.row + drow[i];
			int c = temp.col + dcol[i];
			if (r >= 0 && r < rowSize && c >= 0 && c < colSize	&& board[r][c] == 1) {				
				Enqueue(r, c);
				board[r][c] = curIsland;				
			}
		}			
	}
	curIsland++;
}

int main(void) {
	//freopen("input.txt", "r", stdin);

	register int i, j;
	register int row, col;

	while (1) {

		scanf("%d %d", &colSize, &rowSize);

		if (colSize == 0 && rowSize == 0)
			break;

		for (i = 0; i < rowSize; i++) {
			for (j = 0; j < colSize; j++) {
				scanf("%d", &board[i][j]);
			}
		}
		curIsland = 2;
		for (row = 0; row < rowSize; row++) {
			for (col = 0; col < colSize; col++) {
				if (board[row][col] == 1) {
					Flood(row, col);
				}
			}
		}
		printf("%d\n", curIsland - 2);
	}
	
	return 0;
}

wjsqjawns 4년 전 1

1. queue가 너무 작음. 크기를 주어지는 값에 맞게 조정하고, front와 rear의 값을 조정하는 부분을 변경함.

(queue의 크기가 MAX(650)개밖에 되지 않는데, 주어지는 가로와 세로의 최댓값은 각각 50입니다.)

2. front와 rear의 값을 Flood를 시작할 때마다 각각 0, 0으로 갱신함.

위의 내용대로 수정하니 정답 처리가 되네요.

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

문제

문제

출처

ICPC

반례를 알 수 있을까요?

xaemin 4년 전 0

wjsqjawns 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말