가장 큰 숫자

시간 제한2초메모리 제한512 MB

요약
공백과 별표로 이루어진 격자에 서로 닿지 않게 그려진 여러 숫자 가운데 가장 큰 숫자를 찾아 출력한다.
난이도

보통10점 중 5점

유형
구현, 행렬, 문자열
정답자
아직 제출이 없습니다

문제

여러 개의 숫자들이 주어졌을 때, 이들 중 가장 큰 숫자를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n, m(15 ≤ n ≤ m ≤ 1000)이 주어진다. 다음 n개의 줄에는 공백(' ')과 별 표('*')로 이루어진 숫자들이 주어진다. 각 줄마다 총 m개의 문자가 있다.

모든 숫자들은 어떤 자연수 k에 대해 가로 3k, 세로 5k 크기의 직사각형에 딱 맞게 들어가고, 이 직사각형을 다시 15개의 k × k 정사각형들로 분할할 경우 각 정사각형 안의 문자들은 모두 공백 혹은 별 표 중 한 종류로만 이루어져 있음이 보장된다.

위에서 언급한 숫자를 포함하는 직사각형들에 대해, 어떤 직사각형도 서로 겹쳐져 있지 않다. 또한 어떤 직사각형도 상하좌우 혹은 대각선 방향으로 맞닿아 있지 않다. 가장 큰 숫자는 하나만 주어진다.

출력

첫째 줄에 가장 큰 숫자를 출력한다.

힌트

***  **   **   ***    *
* *   *     *    *   **
* *   *    *    **  * *
* *   *   *      *  ***
***  ***  ***  ***    *

***  *    ***  ***  ***
*    *      *  * *  * *
**   ***   *   ***  ***
  *  * *  *    * *    *
***  ***  *    ***    *

예제1

  1. 예제 1

    입력
    17 27
**                         
  * ******                 
 *  ******  *********      
*       **  *********      
***     **  *********      
      **          ***      
      **          ***      
    **            ***      
    **         ******      
    **         ******      
    **         ******      
                  ***      
    *             ***      
   **             ***      
  * *       *********      
  ***       *********      
    *       *********
    예상 출력
    3