글 읽기 - 토마토 도와주세요...

woobyeng 4년 전 0

반례도 여러개 돌려보고 했는데 도저히 못찾겠네요...

고수님들 도와주세요...

#include<stdio.h>

#define MAX_N 1001

int col, row;
int box[MAX_N][MAX_N] = { 0, };
int front, rear;
const int dx[] = { 0,0,-1,+1 };
const int dy[] = { -1,+1,0,0 };


typedef struct strt {
	int x, y;
}strt;

strt queue[1000000] = { 0, };

void init_Q() {
	front = rear = 0;
}

int empty_Q() {

	if (front == rear) {
		return 1;
	}
	else {
		return 0;
	}
}

int full_Q() {
	if ((front + 1) % MAX_N == rear) {
		return 1;
	}
	else {
		return 0;
	}
}

int in_Q(strt value) {
	if (full_Q()) {
		return 0;
	}
	queue[front].x = value.x;
	queue[front].y = value.y;
	front++;
	if (front == MAX_N) {
		front = 0;
	}
	return 1;
}


int de_Q(strt *value) {
	if (empty_Q()) {
		return 0;
	}
	*value = queue[rear];
	rear++;
	if (rear == MAX_N) {
		rear = 0;
	}
	return 1;
}


int main() {
	int cnt = 0, days = 0 , cnt2=0;
	bool is_update = false;
	bool visited[MAX_N][MAX_N] = { false, };
	bool flag = false;
	init_Q();
	strt tomato;

	scanf("%d %d", &row, &col);

	for (int i = 0; i < col; i++) {
		for (int j = 0; j < row; j++) {
			scanf("%d", &box[i][j]);
			if (box[i][j] == 1) {
				tomato.x = j;
				tomato.y = i;
				in_Q(tomato);
				is_update = true;
				visited[i][j] = true;
				cnt++;
			}
			if (box[i][j] == 0) {
				flag = true;
			}
		}
	}

	while (is_update) {
		strt pos;
		strt next;
		
		for (int i = 0; i < cnt; i++) {
			de_Q(&pos);
			for (int dir = 0; dir < 4; dir++) {
				next.y = pos.y + dy[dir];
				next.x = pos.x + dx[dir];
				if (next.y<0 || next.y>=col || next.x<0 || next.x>=row) {
					continue;
				}
				if (visited[next.y][next.x] != true && box[next.y][next.x] == 0) {
					in_Q(next);
					box[next.y][next.x] = 1;
					visited[next.y][next.x] = true;
					cnt2++;
				}
			}
		}
		if (cnt2 == 0) {
			is_update = false;
		}
		else {
			cnt = cnt2;
			cnt2 = 0;
			days++;
		}
	}

	for (int i = 0; i < col; i++) {
		for (int j = 0; j < row; j++) {
			if (box[i][j] == 0) {
				days = -1;
			}
		}
	}
	if (flag == false) {
		days = 0;
	}
	printf("%d", days);
}

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

문제

문제

출처

ICPC

토마토 도와주세요...

woobyeng 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말