비밀 숫자
면접 대비시간 제한2초메모리 제한512 MB
숫자와 문자가 섞인 격자에서 오른쪽이나 아래로만 이동하는 숫자 경로가 만드는 수 중 가장 큰 수를 찾는다.
문제
각 원소가 숫자('0'-'9') 또는 알파벳 대문자('A'-'Z')인 행렬에 숨겨진 비밀 숫자를 찾아야 한다. 그림 1에서 예시 행렬을 볼 수 있다.
그림 1: 행렬
비밀 숫자와 그 밖의 숫자들은 행렬 안에 십진수 형태의 숫자열로 적혀 있다. D1 D2 ... D**n 형태의 숫자열 중, 각 k (1 <= k < n)에 대해 D**k+1이 행렬에서 D**k의 바로 오른쪽이나 바로 아래에 있는 것만 고려한다. 찾아야 하는 비밀 숫자는 이런 방식으로 만들 수 있는 수 중 가장 큰 수이다.
그림 1의 행렬에서 만들 수 있는 네 개의 수 908820, 23140037, 23900037, 9930이 그림 2에 표시되어 있다. 보다시피 일반적으로 두 개 이상의 수가 같은 부분 수열을 공유할 수 있다. 이 경우 비밀 숫자는 행렬에서 만들 수 있는 모든 수 중 가장 큰 23900037이다.
그림 2: 만들 수 있는 수
반대로 그림 3에 나온 숫자열은 제외된다. 908A2는 알파벳을 포함하고, 23149930의 다섯 번째 숫자는 네 번째 숫자보다 위에 있으며, 90037의 세 번째 숫자는 두 번째 숫자의 오른쪽 아래에 있다.
그림 3: 적절하지 않은 숫자열
주어진 행렬에서 비밀 숫자를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 데이터 세트로 이루어지며, 각 데이터 세트는 행렬 하나를 나타낸다. 각 데이터 세트의 형식은 다음과 같다.
W H
C11C12 ... C1W
C21C22 ... C2W
...
CH1CH2 ... CHW
데이터 세트의 첫 줄에는 두 양의 정수 W와 H가 주어진다. W는 행렬의 너비(열의 개수), H는 행렬의 높이(행의 개수)이다. W+H는 70 이하이다.
첫 줄 다음에는 H개의 줄이 오며, 각 줄은 위에서 아래 순서대로 행렬의 한 행에 해당한다. i번째 행은 왼쪽에서 오른쪽 순서대로 W개의 문자 C**i1C**i2 ... C**iW로 이루어진다. 행렬에는 0이 아닌 숫자가 적어도 하나 있다고 가정할 수 있다.
마지막 데이터 세트 다음에 한 줄에 두 개의 0이 오면 입력의 끝을 나타낸다.
출력
각 데이터 세트마다 비밀 숫자를 한 줄에 출력한다. 앞에 붙은 0은 출력하지 않는다.