글 읽기 - 안전영역 반례좀 찾아주세요 ㅜ

jhko00 7년 전 0

삼차원 배열에 a[i][101][101] (1<=i<=100)인 이차원 배열이 비가 i만큼 올 때 건물을 잠기게 해놓은 배열이고

각 배열마다 일일이 bfs로 영역의 갯수를 확인해 비교해서 가장 큰 값을 출력하도록 했는데

건물 높이가 100 이하니까 비가 100이상 오면 어차피 다 잡기기때문에 100이상은 의미가 없다고 계산하고

건물 높이가 다 1이면 비가 1만 와도 다 잠기니까 안전 영역이 없는건로 생각해서 0이 나오도록 했습니다

각 비가 오는 높이마다 안전 영역의 갯수는 맞게 표시되는데 답이 틀릴 반례가 찾아지지 않아서 질문 올립니다

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
queue<pair<pair<long long int,long long int >,long long int > > q;
queue<pair<pair<long long int,long long int >,long long int > > q2;
long long int n,i,j,k,a[101][101][101],re=0;
long long int maxi(long long int x,long long int y){
	if(x>y)
	return x;
	else
	return y;
}
int main(){
	scanf("%lld",&n);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%lld",&a[0][i][j]);
			for(k=1;k<101;k++){
				if(a[0][i][j]<=k)
					a[k][i][j]=0;
				else
					a[k][i][j]=1;
			}
		}
	}
	for(i=1;i<101;i++){
		long long int t=0;
	//	q.swap(q2);
		swap(q,q2);
		for(j=0;j<n;j++){
			for(k=0;k<n;k++){
				if(a[i][j][k]==1){
					q.push(make_pair(make_pair(j,k),t));
					a[i][j][k]=0;
					while(1){
						if(q.front().first.first>0 && a[i][q.front().first.first-1][q.front().first.second]==1){
							q.push(make_pair(make_pair(q.front().first.first-1,q.front().first.second),t));
							a[i][q.front().first.first-1][q.front().first.second]=0;
						}
						if(q.front().first.first<n-1 && a[i][q.front().first.first+1][q.front().first.second]==1){
							q.push(make_pair(make_pair(q.front().first.first+1,q.front().first.second),t));
							a[i][q.front().first.first+1][q.front().first.second]=0;
						}
						if(q.front().first.second>0 && a[i][q.front().first.first][q.front().first.second-1]==1){
							q.push(make_pair(make_pair(q.front().first.first,q.front().first.second-1),t));
							a[i][q.front().first.first][q.front().first.second-1]=0;
						}
						if(q.front().first.second<n-1 && a[i][q.front().first.first][q.front().first.second+1]==1){
							q.push(make_pair(make_pair(q.front().first.first,q.front().first.second+1),t));
							a[i][q.front().first.first][q.front().first.second+1]=0;
						}
						q.pop();
						if(q.empty()){
							t+=1;
							break;
						}
					}
				}
			}
		}
		re=maxi(re,t);
	}
	printf("%lld\n",re);
	return 0;
}

erin207 7년 전 5

1 1

비가 안 오면 답은 1이 됩니다.

근데 저 소스는 0이 출력됩니다.

jhko00 7년 전 0

erin207님 감사합니다

저는 질문 내용처럼 모든 건물이 1일땐 안전 영역이 0개로 계산했는데 그것때문에 틀렸었군요

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

문제

문제

출처

ICPC

안전영역 반례좀 찾아주세요 ㅜ

jhko00 7년 전 0

erin207 7년 전 5

jhko00 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말