글 읽기 - 치즈문제 도와주세요..

choyj1127 1년 전 0

잘 구현된 것 같고 반례들이랑 TC도 잘 맞는 것같은데 25퍼에서 틀렸습니다 뜨니까 힘드네요..
#include <stdio.h>
#include <stdlib.h>
typedef struct {
	int x;
	int y;
}Queue;
Queue q[100000];
Queue air[100000];
int map[1000][1000];
int result[1000][1000];
int visited[1000][1000];
int N, M;
int total, cnt = 0, melted = 0;
int q_f = 0, q_r = 0, air_f = 0, air_r = 0, nx, ny;
int time = 1;

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

void Input() {
	scanf_s("%d %d", &N, &M);
	for (int i = 0; i < N; i++) { 	//visited: 치즈는 -1, 공기는 0
		for (int j = 0; j < M; j++) {
			scanf_s("%d", &map[i][j]);
			if (map[i][j] == 1) {
				q[q_r].x = i;
				q[q_r].y = j;
				q_r++;
				visited[i][j] = -1;
				cnt++;
			}
		}
	}

	total = cnt; //처음 치즈의 개수 
	if (cnt == 0) {
		printf("0\n");
		printf("0\n");
		exit(0);
	}
}

//바로 옆에 공기가 있다면, 그 이어져있는 공기도 visited가 1이 된다
void OutsideAir() {
	air_f = 0, air_r = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				air[air_r].x = i;
				air[air_r].y = j;
				air_r++;
				visited[i][j] = 0;
			}
		}
	}

	visited[0][0] = 1;
	while (air_f < air_r) {
		int popx = air[air_f].x;
		int popy = air[air_f].y;
		air_f++;

		for (int i = 0; i < 4; i++) {
			nx = popx + dx[i];
			ny = popy + dy[i];

			if (0 <= nx && nx <= N - 1 && 0 <= ny && ny <= M - 1) {
				if (visited[nx][ny] == 1)
					visited[popx][popy] = 1;
			}
		}
	}

	air_f = 0, air_r = 0;
	for (int i = 0; i < N; i++) {
		for (int j = M - 1; j >= 0; j--) {
			if (visited[i][j] == 0) {
				air[air_r].x = i;
				air[air_r].y = j;
				air_r++;
			}
		}
	}

	while (air_f < air_r) {
		int popx = air[air_f].x;
		int popy = air[air_f].y;
		air_f++;

		for (int i = 0; i < 4; i++) {
			nx = popx + dx[i];
			ny = popy + dy[i];

			if (0 <= nx && nx <= N - 1 && 0 <= ny && ny <= M - 1) {
				if (visited[nx][ny] == 1)
					visited[popx][popy] = 1;
			}
		}
	}

	air_f = 0, air_r = 0;
	for (int i = N-1; i >=0; i--) {
		for (int j = M - 1; j >= 0; j--) {
			if (visited[i][j] == 0) {
				air[air_r].x = i;
				air[air_r].y = j;
				air_r++;
			}
		}
	}

	while (air_f < air_r) {
		int popx = air[air_f].x;
		int popy = air[air_f].y;
		air_f++;

		for (int i = 0; i < 4; i++) {
			nx = popx + dx[i];
			ny = popy + dy[i];

			if (0 <= nx && nx <= N - 1 && 0 <= ny && ny <= M - 1) {
				if (visited[nx][ny] == 1)
					visited[popx][popy] = 1;
			}
		}
	}

	air_f = 0, air_r = 0;
	for (int i = N-1; i >=0; i--) {
		for (int j = 0; j <=M-1; j++) {
			if (visited[i][j] == 0) {
				air[air_r].x = i;
				air[air_r].y = j;
				air_r++;
			}
		}
	}

	while (air_f < air_r) {
		int popx = air[air_f].x;
		int popy = air[air_f].y;
		air_f++;

		for (int i = 0; i < 4; i++) {
			nx = popx + dx[i];
			ny = popy + dy[i];

			if (0 <= nx && nx <= N - 1 && 0 <= ny && ny <= M - 1) {
				if (visited[nx][ny] == 1)
					visited[popx][popy] = 1;
			}
		}
	}
}

//만약, 치즈의 위치의 상하좌우에 visited=1인 외부공기가 있다면 치즈는 녹고, 해당 치즈의 visited=2로한다.
void MeltingOutdoorCheese() {
	while (q_f < q_r) {
		int popx = q[q_f].x;
		int popy = q[q_f].y;
		q_f++;

		int flag = 0;
		for (int i = 0; i < 4; i++) {
			nx = popx + dx[i];
			ny = popy + dy[i];

			if (0 <= nx && nx <= N - 1 && 0 <= ny && ny <= M - 1) {
				if (map[nx][ny] == 0 && visited[nx][ny] == 1)
					flag = 1;
			}
		}
		if (flag == 1) {
			visited[popx][popy] = 2;
			map[popx][popy] = 0;
			result[popx][popy] += 1;
			time = result[popx][popy];

			melted++;
		}
	}
}

//visited=2인 (방금 막 녹은 치즈)는 visited=1로 완전한 공기로 변환
void ArrangeVisited() {
	if (melted < total) {
		q_f = 0, q_r = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visited[i][j] == 2) {
					visited[i][j] = 1;
				}
				else if (map[i][j] == 1) {
					q[q_r].x = i;
					q[q_r].y = j;
					q_r++;
					result[i][j] += 1;
				}
			}
		}
	}
}

void Output() {
	int last = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (result[i][j] == time)
				last++;
		}
	}
	printf("%d\n", time);
	printf("%d\n", last);
}

int main() {
	Input();
	OutsideAir();

	while (melted < total) {
		MeltingOutdoorCheese();
		OutsideAir();
		ArrangeVisited();
	}

	Output();
	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

치즈문제 도와주세요..

choyj1127 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
