글 읽기 - 이 코드 보고 해결해주실 고수님 계신가요 ㅠㅠ

lg8375 7년 전 0

높이 9에서 한칸씩 내려오면서 둘러싸서 수영장을 만들어봤는데요

생각해낼수있는 반례가 없네요 ㅠㅠ 어떤 논리가 오류가 있는지도 모르겠습니다

도와주세여 ㅜㅜ

#include<stdio.h>

int arr[60][60];//입력받는배열
int chk[60][60];//활용할 주 맵
int chk_chk[60][60];//방문여부확인용
int chk_use[60][60];//방문여부확인용
int dont[60][60];//땅이 0일경우 흡수하는거 용도
int xx[1000000], xy[1000000];//큐 x y 좌표
int st, ed;//ed가 st를 따라가면서 큐 돌림
int move1[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int move2[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };
void inque(int a, int b)
{
	xx[st] = a, xy[st] = b;
	st++;
}
int main(void)
{
	int N=0, M=0, i=0, j=0, k=0, as=0;
	int min = 10000;
	int l=0, m=0;
	int height = 9;
	int sum = 0;

	scanf("%d%d", &N, &M);

	for (i = 1; i <= N; i++){
		for (j = 1; j <= M; j++){
			scanf("%1d", &arr[i][j]);
		}
	}


	for (as = 9; as >= 1; as--){
		height = as;
		for (i = 1; i <= N; i++){
			for (j = 1; j <= M; j++){
				if (chk[i][j] != 100 && arr[i][j] == height){
					st = 1, ed = 0;
					xx[ed] = i, xy[ed] = j;
					chk[i][j] = height;
					chk_use[i][j] = 1;
					while (st > ed){//(i,j)에서 연결된 수영장을 찾는 큐
						for (k = 0; k <= 7; k++){
							if (chk[xx[ed] + move1[k]][xy[ed] + move2[k]] != 100 && arr[xx[ed] + move1[k]][xy[ed] + move2[k]] >= height&&chk_use[xx[ed] + move1[k]][xy[ed] + move2[k]] == 0 && xx[ed] + move1[k] >= 1 && xx[ed] + move1[k] <= N&&xy[ed] + move2[k] >= 1 && xy[ed] + move2[k] <= M){
								inque(xx[ed] + move1[k], xy[ed] + move2[k]);
								if (chk[xx[ed] + move1[k]][xy[ed] + move2[k]] < height){
									chk[xx[ed] + move1[k]][xy[ed] + move2[k]] = height;
								}
								chk_use[xx[ed] + move1[k]][xy[ed] + move2[k]] = 1;
							}
						}
						ed++;
					}
					st = 1, ed = 0;
					xx[ed] = 0, xy[ed] = 0;
					chk_chk[0][0] = 1;
					chk[0][0] = -1;
					while (st > ed){//0,0 으로부터 '-1'값을 흘려보내서 수영장내부가 둘러싸여있는지 확인하는 큐
						for (k = 0; k <= 3; k++){
							if (chk[xx[ed] + move1[k]][xy[ed] + move2[k]] != 100 && chk[xx[ed] + move1[k]][xy[ed] + move2[k]] == 0 && chk_chk[xx[ed] + move1[k]][xy[ed] + move2[k]] == 0 && xx[ed] + move1[k] >= 0 && xx[ed] + move1[k] <= N + 1 && xy[ed] + move2[k] >= 0 && xy[ed] + move2[k] <= M + 1){
								inque(xx[ed] + move1[k], xy[ed] + move2[k]);
								chk[xx[ed] + move1[k]][xy[ed] + move2[k]] = -1;
								chk_chk[xx[ed] + move1[k]][xy[ed] + move2[k]] = 1;
							}
						}
						ed++;
					}
					for (l = 0; l <= N + 1; l++){
						for (m = 0; m <= M + 1; m++){
							if (chk[l][m] == 0){
								chk[l][m] = 100;//이곳은 수영장임이 입증됨
							}
							if (chk[l][m] == -1){
								chk[l][m] = 0;//다음에도 -1 을 흘리도록 초기화
							}
							chk_chk[l][m] = 0;
							chk_use[l][m] = 0;
						}
					}

				}

			}

		}

	}

	for (i = 1; i <= N; i++){
		for (j = 1; j <= M; j++){
			if (arr[i][j] == 0&&chk[i][j]==100){//수영장이지만 높이가 0이라서 그 수영장의 모든 물이 없어지는 경우
				st = 1, ed = 0;
				xx[ed] = i, xy[ed] = j;
				chk_chk[i][j] = 1;
				while (st > ed){
					dont[xx[ed]][xy[ed]] = 1;
					for (k = 0; k <= 3; k++){
						if (chk[xx[ed] + move1[k]][xy[ed] + move2[k]] == 100 && chk_chk[xx[ed] + move1[k]][xy[ed] + move2[k]] == 0){
							inque(xx[ed] + move1[k], xy[ed] + move2[k]);
							chk_chk[xx[ed] + move1[k]][xy[ed] + move2[k]] = 1;
						}
					}
					ed++;
				}

			}
		}
	}

	for (i = 1; i <= N; i++){
		for (j = 1; j <= M; j++){
			if (chk[i][j] == 100&&dont[i][j]==0){
				for (k = 0; k <= 3; k++){
					if (min > chk[i + move1[k]][j + move2[k]]){
						min = chk[i + move1[k]][j + move2[k]];
					}
				}
				chk[i][j] = min;
				sum = sum + min - arr[i][j];
				min = 10000;
			}
		}
	}


	printf("%d", sum);
	return 0;



}

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

문제

문제

출처

ICPC

이 코드 보고 해결해주실 고수님 계신가요 ㅠㅠ

lg8375 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말