#include <stdio.h>
int x,y,box[1002][1002]={},to[1000001]={},too[1000001]={},qu=0,de=0,max=-1,maxdays = 0,days = 0;
int view(){
for(int i = 0 ; i < y ; i++){
for(int j = 0 ; j < x ; j++){
if(box[i][j]==0){
return -1;
}
}
}
return max;
}
int test(){
printf("\n");
for(int i = 0 ; i < y ; i++){
for(int j = 0 ; j < x ; j++){
printf("%d ",box[i][j]);
}
printf("\n");
}
for(int i = de ; i < qu ; i++){
printf("(%d,%d)",to[i],too[i]);
}
printf("\n");
printf("%d %d %d\n",max,days,maxdays);
}
void push(int a,int b){
to[qu]=a;
too[qu++]=b;
}
int BFS(){
while(1){
if(de >= qu)
return 0;
days=maxdays;
for(maxdays=0;days>0;days--){
int xx,yy;
xx = too[de];
yy = to[de++];
box[yy][xx] = 1;
if(yy<y-1&&box[yy+1][xx]==0){
push(yy+1,xx); maxdays++;box[yy+1][xx]=1;
}
if(yy>0&&box[yy-1][xx]==0){
push(yy-1,xx); maxdays++;box[yy-1][xx]=1;
}
if(xx<x-1&&box[yy][xx+1]==0){
push(yy,xx+1); maxdays++;box[yy][xx+1]=1;
}
if(xx>0&&box[yy][xx-1]==0){
push(yy,xx-1); maxdays++;box[yy][xx-1]=1;
}
}
max++;
}
}
int main(){
scanf("%d %d",&x,&y);
for(int i = 0 ; i < y ; i++){
for(int j = 0 ; j < x ; j++){
scanf("%d",&box[i][j]);
if(box[i][j]==1){
push(i,j); maxdays++;
}
}
}
BFS();
int a = view();
printf("%d",a);
}
top of page
실제 작동 상태를 확인하려면 라이브 사이트로 이동하세요.
수정: 2023년 11월 18일
BFS 코마토(고등)
BFS 코마토(고등)
댓글 0개
좋아요
댓글(0)
bottom of page