#include <stdio.h>
int m,n,arr[2222][2222]={},day=0,cnt=0,tom=0;
int queue[2][1111]={},front=-1,back=-1,p=0;
void push(int x, int y)
{
if(x<=-1||x>=n||y<=-1||y>=m||arr[x][y]!=0)
{
return ;
}
else
{
// printf("(%d %d),",x,y);
queue[0][++back]=x;
queue[1][back]=y;
arr[x][y]=1;
// printf("%d\n",back);
}
}
void bfs()
{
while(1)
{
// printf("p%d ",p);
front++;
int x=queue[0][front];
int y=queue[1][front];
push(x+1,y);
push(x-1,y);
push(x,y-1);
push(x,y+1);
// printf("front %d, p %d\n",front,p);
if(front==p)
{
// printf("break\n");
break;
}
}
return ;
}
int main()
{
int i,j;
scanf("%d %d",&m,&n);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&arr[i][j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(arr[i][j]==1)
{
queue[0][++back]=i;
queue[1][back]=j;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(arr[i][j]!=-1)
{
tom++;
}
}
}
/////////////////////////////////
while(1)
{
p=back;
bfs();
// printf("\n\n\na");
day++;
if(back>=tom-1)
{
break;
}
cnt=0;
}
printf("%d",day);
return 0;
}
(테스트케이스 6#)
'-' => '-1'
142 15
- 0 0 0 0 0 0 1 0 0 - 0 - 1 0 - - 0 0 1 0 - - 0 0 0 0 0 1 - - 0 - 0 0 0 0 1 0 0 1 0 0 0 0 0 0 - 0 0 0 - 0 1 - - 0 0 0 0 0 0 0 1 0 0 - 0 0 1 0 - 0 0 0 0 0 0 - 0 - 0 0 1 - 0 0 0 0 - 0 0 0 0 0 - 0 0 1 0 0 - - 0 - 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 - 0 0 1 0 0 0 - 0 0 0 0 0 - 0 0 0 0 - 1 0 0 0 0 1 0 - 0 1 - 1 0 0 1 - 0 0 0 0 0 0 0 0 0 0 0 1 0 0 - 0 0 0 1 1 0 - 0 0 0 0 1 0 0 0 0 - 0 0 0 0 - 0 - 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 - 0 0 0 - 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 - 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 - 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - 0 0 1 0 0 0 0 0 0 1 0 - 1 1 0 0 1 1 0 0 0 0 1 - 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - 1 0 1 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 - 0 0 0 0 0 1 0 0 0 0 - 0 - 0 - 1 0 - - 0 0 1 0 - 0 0 1 - 0 0 0 - 0 1 0 0 0 1 - - 0 0 - 0 0 0 - - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - 0 - 0 0 0 0 0 - 1 0 0 0 1 0 0 - 0 0 0 0 1 0 0 1 0 0 0 - 0 0 0 0 0 1 0 0 0 0 0 - - 1 0 0 0 0 0 0 - 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 - 0 0
1 0 0 0 0 0 0 0 - 0 0 1 0 0 0 0 0 0 - 1 0 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 - 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 - 0 0 0 - 0 0 1 0 0 0 - - 0 0 0 0 0 1 0 - - 0 - 0 0 0 0 - 1 0 - 0 1 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 - 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 - 0 1 0 0 1 0 - 1 0 - 0 0 - 0 0 0 0 0 0 0 0 1 1 0 - 0 0 0 - 0 0 0 - 0 0 0 0 0 0 - - 0 0 0 0 0 0 1 1 0 0 - 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 - 0 1 1 0 - 1 0 - 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 - 0 0
1 0 0 0 0 0 0 0 0 - 0 0 1 0 0 0 0 0 0 0 - 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 1 - 0 0 1 0 0 0 0 0 - - - 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 - - - 0 - - 1 0 0 0 0 0 0 1 - - 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 - 1 0 0 0 - 0 0 1 0 0 0 0 0 - 0 0 0 - 1 0 0 0 0 - 0 0 0 0 0 0 0
- 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 - - 1 - 0 0 0 1 0 0 0 0 - - 0 0 - - 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 - 0 - 0 0 - 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 - - 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 - 0 0 - 0 - 0 0 0 0 0 0 - - 1 0 0 0 0 - 0 0 -
0 0 0 0 1 - 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 - 0 0 - 1 0 0 0 0 0 - 0 0 0 0 - 0 1 0 0 - 0 - 0 0 1 0 0 0 0 0 - 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 1 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 - 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 - 0 0 0 - 0 0 0 1 0 - 0 1 - 0 0 - 0 0 0 0 0 0 - 0 0 0 0 0 0 0 0 0 - 0 - 0 0 - 0 1 0 0 - 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 0 0 1 0 1 - 0 0 - 0 0 0 0 - 1 0 0 0 0 - 1 1 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 - 0 0 0 0 0 1 0 0 0 0 - 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 - - 0 0 0 1 0 0 0 0 0 1 0 0 1 - 0 - 0 0 0 0 0 0 0 - 0 0 0 - 0 0 0 0 - 0 0 0 0 0 - 0 1 0 0 0 1 0 0 1 0 0 0 0 0 - 0 0 0 0 0 0 1 0 - - 0 0 0 0 - 0 0 0 - 0 0 0 0 0 0 1 1 0 0 1 0 - - - - 0 0 0 - 0 0 0 0 0 0 0 0 1 0 0 0 - 0 0 - 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 - 0 0 0 1 - 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 - 0 1 0 0 0 0 - 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 - 1 0 - 0 0 0 0 0 0 0 - 0 0 - 0 0 0 - 0 0 0 1 0 0 0 0 0 0 - 1 0 - 0 0 0 - 0 - 0 1 0 - 0 0 0 0 - 1 0 1 0 0 0 - 0 - 0 1 - 0 0 0 0 - - 0 1 - - 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0 0 0 0 - 0 1 0 0 0 0 0 0 0 - 1 0 0 - 0 0 0 0 0 1 0 - 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 - 0 0 1 - 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 - 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 - 0 0 0 0 1 0 0 0 0 0 - 0 0 0 0 1 0 1 0 - 0 0 0 0 0 0 0 - 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 - 1 0 0 0 0 - 0 0 0 0 1 0 0 0 - 0 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 - - 0 0 1 0 - 0 0 0 0 - 0 0 1 0 0 0 0 0 0 0 0 0 0 1 - 0 - - 0 0 1 0 0 0 - - 0 0 0 0
- 0 0 - - 0 - 0 1 0 - 0 0 0 0 0 - - 0 1 1 0 0 0 0 1 0 0 0 0 0 - 0 0 1 - 0 - - 0 0 0 0 1 0 0 0 0 0 0 0 - - - 0 1 0 1 0 0 0 0 0 0 0 0 0 - 1 - - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 - 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 - 0 0 0 0 0 0 0