oj.uz

Submission #4276

# Submission time Handle Problem Language Result Execution time Memory
4276 2013-09-10T12:55:22 Z ansol4328 토마토 (KOI13_tomato) C++
16 / 16
 140 ms 71432 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 0 ms 71432 KB Output is correct

Subtask #2
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 0 ms 71432 KB Output is correct

Subtask #3
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 0 ms 71432 KB Output is correct

Subtask #4
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 4 ms 71432 KB Output is correct
2 Correct 4 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 0 ms 71432 KB Output is correct

Subtask #5
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 4 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 4 ms 71432 KB Output is correct
4 Correct 4 ms 71432 KB Output is correct

Subtask #6
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 4 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 4 ms 71432 KB Output is correct

Subtask #7
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 44 ms 71432 KB Output is correct
2 Correct 24 ms 71432 KB Output is correct
3 Correct 12 ms 71432 KB Output is correct
4 Correct 12 ms 71432 KB Output is correct

Subtask #8
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 56 ms 71432 KB Output is correct
2 Correct 48 ms 71432 KB Output is correct
3 Correct 8 ms 71432 KB Output is correct
4 Correct 8 ms 71432 KB Output is correct

Subtask #9
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 36 ms 71432 KB Output is correct
2 Correct 92 ms 71432 KB Output is correct
3 Correct 12 ms 71432 KB Output is correct
4 Correct 72 ms 71432 KB Output is correct

Subtask #10
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 140 ms 71432 KB Output is correct
2 Correct 136 ms 71432 KB Output is correct
3 Correct 128 ms 71432 KB Output is correct
4 Correct 88 ms 71432 KB Output is correct