글 읽기 - 빙산문제 도저히 어느 부분이 틀린지 모르겠어요

mw9911 5년 전 0

ㅁ모든 케이스들이 되는것 같은데 어느 부분이 틀린지 모르겠어요

#include<stdio.h>
#include<string.h>
int s, e, X, Y, M, N, X1, Y1;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int map[301][301];
int Mchk[301][301];
typedef struct kim {
	int x;
	int y;
}mw;
mw q[10001];
mw pop() {
	return q[s++];
}
void push(mw a) {
	Mchk[a.y][a.x] = 1;
	q[e++] = a;
}
void BFS() {
	while (s != e) {
		mw cur = pop();
		mw temp;
		for (int i = 0; i < 4; i++) {
			X = cur.x + dx[i];
			Y = cur.y + dy[i];
			if (X >= 0 && X < M&&Y >= 0 && Y < N) {
				if (map[Y][X] > 0 && Mchk[Y][X] == 0) {
					temp = { X,Y };
					push(temp);
				}
				
			}
		}
	}
}
mw qt[10001];
int st;
int et;
int main() {
	int count = 0;
	int ch = 0;
	int ch2 = 0;
	int ga = 0;
	scanf("%d %d", &N, &M);
	mw temp;

	for (int r = 0; r < N; r++) {
		for (int r1 = 0; r1 < M; r1++) {
			scanf("%d", &map[r][r1]);
			if (map[r][r1] > 0) {
				
				X1 = r1;
				Y1 = r;
				temp = { r1,r };
				push(temp);
			}
		}
	}
	memset(Mchk, 0, sizeof(Mchk));

	for (int z = 0; z < e; z++) {
		if (Mchk[q[z].y][q[z].x] == 0 && map[q[z].y][q[z].x] > 0) {
			et = 0; st = 0;
			Mchk[q[z].y][q[z].x] = 1;
			qt[et++] = { q[z].x,q[z].y };
			ch++;
			while (st != et) {
				for (int j = 0; j < 4; j++) {
					X = qt[st].x + dx[j];
					Y = qt[st].y + dy[j];
					if (X >= 0 && X < M&&Y >= 0 && Y < N) {
						if (map[Y][X] > 0 && Mchk[Y][X] == 0) {
							Mchk[Y][X] = 1;

							qt[et++] = { X,Y };
						}
					}
				}
				st++;
			}
		}
	}//처음부터 분리 되어있는지 확인
	if (ch >= 2) { 
		printf("%d", 0);
		return 0;
	}
	memset(Mchk, 0, sizeof(Mchk));
	memset(q, 0, sizeof(q));
	while (ch == 1) {
		ch = 0;
		memset(Mchk, 0, sizeof(Mchk));
		mw temp = { X1,Y1 };
		push(temp);
		BFS();//큐에 빙하부분 저장
		for (int i = 0; i < e; i++) {
			for (int j = 0; j < 4; j++) {
				X = q[i].x + dx[j];
				Y = q[i].y + dy[j];
				if (X >= 0 && X < M&&Y >= 0 && Y < N) {
					if (map[Y][X] == 0 && Mchk[Y][X] == 0&&map[q[i].y][q[i].x]>0) {
						map[q[i].y][q[i].x]--;
					}
				}
				if (map[q[i].y][q[i].x] > 0) {
					X1 = q[i].x;
					Y1 = q[i].y;
				}
			}
		}//큐에서 빙하부분을 하나씩 꺼내서 녹임
		memset(Mchk, 0, sizeof(Mchk));
		for (int z = 0; z < e; z++) {
			if (Mchk[q[z].y][q[z].x] == 0 && map[q[z].y][q[z].x] > 0) {
				et = 0; st = 0;
				Mchk[q[z].y][q[z].x] = 1;
				qt[et++] = { q[z].x,q[z].y };
				ch++;
				ch2++;
				while (st != et) {
					for (int j = 0; j < 4; j++) {
						X = qt[st].x + dx[j];
						Y = qt[st].y + dy[j];
						if (X >= 0 && X < M&&Y >= 0 && Y < N) {
							if (map[Y][X] > 0 && Mchk[Y][X] == 0) {
								Mchk[Y][X] = 1;

								qt[et++] = { X,Y };
							}
						}
					}
					st++;
				}
			}
		}//분리되어 있는지 확인
		
		memset(qt, 0, sizeof(qt));
		s = 0;
		e = 0;
		count++;
		if (ch >= 2) break;

	}
	if (ch >= 2) {
		printf("%d", count);
		return 0;

	}
	if (ch == 0) {
		printf("0");
		return 0;
	}
}

luniro 5년 전 0

출력:
0

정답:
4

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

문제

문제

출처

ICPC

빙산문제 도저히 어느 부분이 틀린지 모르겠어요

mw9911 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말