정사각형 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다. 이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다. 핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다.

현재 정원의 상태를 담은 2차원 배열 garden이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 함수를 작성해주세요.

매개변수 설명

현재 정원 상태를 담은 2차원 배열 garden이 solution 함수의 매개변수로 주어집니다.

• 정원의 한 변의 길이는 2 이상 100 이하입니다.
• 정원 상태를 담은 2차원 배열 garden의 원소는 0 또는 1 입니다.
• 이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
• 정원에 최소 꽃 한 개는 피어 있습니다.

return 값 설명

꽃이 모두 피는데 며칠이 걸리는지 return 합니다.

예제

예제 설명

예제 #1
첫 날 정원은 아래와 같습니다.

1일이 지난 정원의 상태는 아래와 같습니다.

2일이 지난 정원의 상태는 아래와 같습니다.

따라서, 2일이 지나면 정원의 모든 꽃이 핍니다.

예제 #2
첫 날 화단의 상태는 아래와 같습니다.

따라서, 0일이 지나면 정원의 모든 꽃이 핍니다.