#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[1010][1010];
int row, col;
int time;
 
queue<pair<intint>> q;
int visited[1010][1010];
 
int dx[4= {-1100};
int dy[4= {00-11};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
void tomato()
{
    int cnt = q.size();
    
    while(cnt--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0 && map[xpos][ypos] == 0)
            {
                map[xpos][ypos] = 1;
                
                visited[xpos][ypos] = visited[x][y] + 1;
                q.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B7576_input.txt", "r", stdin);
    
    cin >> col >> row;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == 1)
            {
                visited[i][j] = 1;
                q.push({i, j});
            }
        }
    }
    
    while(1)
    {
        if(check() == 1)
        {
            cout << time;
            break;
        }
        
        if(q.empty())
        {
            cout << "-1";
            break;
        }
        
        tomato();
        
        time++;
    }
    
    return 0;
}
cs

+ Recent posts