Submission #4276

#	Time	Username	Problem	Language	Result	Execution time	Memory
4276		ansol4328	토마토 (KOI13_tomato)	C++98	16 / 16	140 ms	71432 KiB

tomato

#include<stdio.h> 
  
int n, m, xy[1002][1002]; 
int q[4000002][4], f, r; 
int time[1002][1002]; 
int max; 
  
int input() 
{ 
    int i, j; 
  
    scanf("%d %d",&m,&n); 
    for(i=1 ; i<=n ; i++) 
    { 
        for(j=1 ; j<=m ; j++) 
        { 
            scanf("%d",&xy[i][j]); 
            time[i][j]=2100000000; 
            if(xy[i][j]==1) 
            { 
                r++; 
                q[r][1]=i; 
                q[r][2]=j; 
                time[i][j]=0; 
            } 
        } 
    } 
    return 0; 
} 
  
int bfs() 
{ 
   int i, j; 
   int x, y; 
   int dy[4]={-1,0,1,0}; 
   int dx[4]={0,1,0,-1}; 
  
   do
   { 
       f++; 
       y=q[f][1]; 
       x=q[f][2]; 
       for(i=0 ; i<4 ; i++) 
       { 
           if(x+dx[i]>=1 && x+dx[i]<=m && y+dy[i]>=1 && y+dy[i]<=n && xy[y+dy[i]][x+dx[i]]==0 && time[y+dy[i]][x+dx[i]]>time[y][x]+1) 
           { 
               r++; 
               q[r][1]=y+dy[i]; 
               q[r][2]=x+dx[i]; 
               time[y+dy[i]][x+dx[i]]=time[y][x]+1; 
           } 
       } 
   }while(f<r); 
   for(i=1 ; i<=n ; i++) 
   { 
       for(j=1 ; j<=m ; j++) 
       { 
           if(time[i][j]>max && xy[i][j]>=0) 
           { 
               max=time[i][j]; 
           } 
       } 
   } 
   return 0; 
} 
  
int output() 
{ 
    if(max==2100000000) 
    { 
        printf("-1"); 
    } 
    else
    { 
        printf("%d",max); 
    } 
    return 0; 
} 
  
int main() 
{ 
    input(); 
    bfs(); 
    output(); 
    return 0; 
} 

• Subtask 1: 1.6 / 1.6
• Subtask 2: 1.6 / 1.6
• Subtask 3: 1.6 / 1.6
• Subtask 4: 1.6 / 1.6
• Subtask 5: 1.6 / 1.6
• Subtask 6: 1.6 / 1.6
• Subtask 7: 1.6 / 1.6
• Subtask 8: 1.6 / 1.6
• Subtask 9: 1.6 / 1.6
• Subtask 10: 1.6 / 1.6