Problem:


The Secret Number

Your job is to find out the secret number hidden in a matrix,
each of whose element is a digit ('0'-'9') or a letter
('A'-'Z').  You can see an example matrix in Figure 1.

Figure 1:  A Matrix

The secret number and other non-secret ones are coded in a
matrix as sequences of digits in a decimal format.  You should
only consider sequences of digits D1
D2 ... Dn such that
Dk+1 (1 <= k < n)
is either right next to or immediately below
Dk in the matrix.  The secret you are
seeking is the largest number coded in this manner.

Four coded numbers in the matrix in Figure 1, i.e., 908820,
23140037, 23900037, and 9930, are depicted in Figure 2.  As you
may see, in general, two or more coded numbers may share a
common subsequence.  In this case, the secret number is
23900037, which is the largest among the set of all coded numbers
in the matrix.

Figure 2: Coded Numbers

In contrast, the sequences illustrated in Figure 3 should be
excluded: 908A2 includes a letter; the fifth digit of 23149930
is above the fourth; the third digit of 90037 is below right of
the second.

Figure 3: Inappropriate Sequences

Write a program to figure out the secret number from a given
matrix.

Input

The input consists of multiple data sets, each data set
representing a matrix.  The format of each data set is as
follows.

W H

C11C12 ... C1W

C21C22 ... C2W

...

CH1CH2 ... CHW

In the first line of a data set, two positive integers W
and H are given.  W indicates the width (the
number of columns) of the matrix, and H indicates the
height (the number of rows) of the matrix.  W+H is less
than or equal to 70.

H lines follow the first line, each of which corresponds
to a row of the matrix in top to bottom order.  The i-th
row consists of W characters
Ci1Ci2
... CiW in left to right order.  You may
assume that the matrix includes at least one non-zero digit.

Following the last data set, two zeros in a line indicate the
end of the input.

Output

For each data set, print the secret number on a line.  Leading zeros
should be suppressed.

Sample Input

7 4
9R2A993
0E314A0
8A900DE
820R037
6 7
JH03HE
ID7722
0DA1AH
30C9G5
99971A
CA7EAI
AHLBEM
20 2
A1234567891234CBDEGH
BDEDF908034265091499
0 0

Output for the Sample Input

23900037
771971
12345908034265091499



Sample input:
7 4
9R2A993
0E314A0
8A900DE
820R037
6 7
JH03HE
ID7722
0DA1AH
30C9G5
99971A
CA7EAI
AHLBEM
20 2
A1234567891234CBDEGH
BDEDF908034265091499
0 0


Sample output:
23900037
771971
12345908034265091499

Submission status: Accepted

Solution code:
def isValid(row, col, ROWS, COLS):
    return row >= 0 and row < ROWS and col >= 0 and col < COLS

def search(matrix, row, col, ROWS, COLS, memo):
    if (row, col) in memo:
        return memo[(row, col)]
    
    numStrA = ''
    numStrB = ''

    rr = row + 1
    cc = col
    if isValid(rr, cc, ROWS, COLS) and matrix[rr][cc].isdigit():
        numStrA = search(matrix, rr, cc, ROWS, COLS, memo)

    rr = row
    cc = col + 1
    if isValid(rr, cc, ROWS, COLS) and matrix[rr][cc].isdigit():
        numStrB = search(matrix, rr, cc, ROWS, COLS, memo)

    numStrA = matrix[row][col] + numStrA
    numStrB = matrix[row][col] + numStrB

    if len(numStrA) > len(numStrB):
        val = numStrA
    elif len(numStrB) > len(numStrA):
        val = numStrB
    else:
        if numStrA > numStrB:
            val = numStrA
        else:
            val = numStrB

    memo[(row, col)] = val
    return val

if __name__ == '__main__':
    while True:
        COLS, ROWS = [ int(x) for x in list(filter(lambda x: x != '', \
            input().strip().split(' '))) ]
        if ROWS == 0 and COLS == 0:
            break

        matrix = []
        for _ in range(ROWS):
            matrix.append(input().strip())
        
        maxNum = 0
        memo = {}
        for row in range(ROWS):
            for col in range(COLS):
                if matrix[row][col].isdigit() and matrix[row][col] != '0':
                    maxNum = max(maxNum, int(search(matrix, row, col, ROWS, COLS, memo)))

        print(maxNum)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main(w, h):
    field = [list(input()) for i in range(h)]
    d = defaultdict(str)
    for y in range(h - 1, -1, -1):
        for x in range(w - 1, -1, -1):
            if "0" <= field[y][x] <= "9":
                d[(x, y)] = field[y][x]
    for y in range(h - 1, -1, -1):
        for x in range(w - 1, -1, -1):
            if "0" <= field[y][x] <= "9":
                if len(d[(x + 1, y)]) == len(d[(x, y + 1)]):
                    d[(x, y)] = field[y][x] + max(d[(x + 1, y)], d[(x, y + 1)])
                elif len(d[(x + 1, y)]) < len(d[(x, y + 1)]):
                    d[(x, y)] = field[y][x] + d[(x, y + 1)]
                else:
                    d[(x, y)] = field[y][x] + d[(x + 1, y)]
    ans = 0
    for v in d.values():
        if v == "":
            continue
        ans = max(ans, int(v))
    print(ans)

while 1:
    w, h = map(int, input().split())
    if h == w == 0:
        break
    main(w, h)

Submission status: Accepted

Solution code:
import sys
from collections import deque

W,H,C = None,None,None
mmax = None

def main():
    global W,H,C,mmax

    while True:
        W,H = map(int,input().split())
        if not W and not H:
            return
        C = []
        mmax = [[-1]*(W+1) for _ in range(H+1)]
        for _ in range(H):
            C.append(list(input()))
        # visualize(C)

        num = 0

        # for i in range(H):
        #     for j in range(W):
        #         if mmax[i][j] != -1:
        #             continue
        #         print("------", i, j, "--------")
        #         num = max(num, bfs(i,j))

        for i in reversed(range(H)):
            for j in reversed(range(W)):
                if mmax[i][j] != -1:
                    continue
                num = max(num, bfs(i,j))
        
        print(num)


def bfs(y,x):
    global W,H,C,mmax

    if not C[y][x].isdigit():
        return 0

    l = []
    queue = deque(l)
    dd = [(0,-1), (-1,0)]
    num = 0

    queue.appendleft((C[y][x],(y,x)))
    mmax[y][x] = int(C[y][x])

    while len(queue) != 0:
        s, (uy,ux) = queue.pop()
        for dy,dx in dd:
            vy,vx = uy+dy, ux+dx
            if not (0 <= vy < H and 0 <= vx < W):
                num = max(num, mmax[uy][ux])
                continue
            if C[vy][vx].isdigit():
                n = int(C[vy][vx]+s)
                if mmax[vy][vx] < n:
                    queue.appendleft((C[vy][vx]+s, (vy,vx)))
                    mmax[vy][vx] = n
            else:
                num = max(num, mmax[uy][ux])

    return num


# def bfs(y,x): # h w
#     global W,H,C,mmax

#     if not C[y][x].isdigit():
#         return 0

#     l = []
#     queue = deque(l)
#     dd = [(0,1), (1,0)]
#     num = 0

#     queue.appendleft((C[y][x],(y,x)))
#     mmax[y][x] = int(C[y][x])

#     while len(queue) != 0:
#         print(len(queue))
#         s, (uy,ux) = queue.pop()
#         for dy,dx in dd:
#             vy,vx = uy+dy, ux+dx
#             if not (0 <= vy < H and 0 <= vx < W):
#                 num = max(num, mmax[uy][ux])
#                 continue
#             if C[vy][vx].isdigit():
#                 n = int(s+C[vy][vx])
#                 if mmax[vy][vx] < n:
#                     queue.appendleft((s+C[vy][vx], (vy,vx)))
#                     mmax[vy][vx] = n
#             else:
#                 num = max(num, mmax[uy][ux])

#     return num


def visualize(mmap):
    for row in mmap:
        print(" ".join(row))

            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#2005_c
"""
n = int(input())
k = list("mcxi")
for i in range(n):
    d = {"m":0,"c":0,"x":0,"i":0}
    a,b  = input().split()
    a = list(a)
    b = list(b)
    a.insert(0,1)
    b.insert(0,1)
    for j in range(1,len(a)):
        if a[j] in k:
            if a[j-1] in k:
                d[a[j]] += 1
            else:
                d[a[j]] += int(a[j-1])
    for j in range(1,len(b))[::-1]:
        if b[j] in k:
            if b[j-1] in k:
                d[b[j]] += 1
            else:
                d[b[j]] += int(b[j-1])
            if d[b[j]] >= 10:
                l = b[j]
                while d[l] >= 10:
                    d[l] -= 10
                    l = k[k.index(l)-1]
                    d[l] += 1
    for j in k:
        if d[j]:
            if d[j] == 1:
                print(j,end = "")
            else:
                print(str(d[j])+j,end = "")
    print()
"""

#2017_c
"""
while 1:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    s = [list(map(int, input().split())) for i in range(h)]

    ans = 0
    for u in range(h):
        for d in range(u+2,h):
            for l in range(w):
                for r in range(l+2,w):
                    m = float("inf")
                    for i in range(u,d+1):
                        m = min(m,s[i][l],s[i][r])
                    for i in range(l,r+1):
                        m = min(m,s[u][i],s[d][i])
                    f = 1
                    su = 0
                    for i in range(u+1,d):
                        for j in range(l+1,r):
                            su += (m-s[i][j])
                            if s[i][j] >= m:
                                f = 0
                                break
                        if not f:
                            break
                    if f:
                        ans = max(ans,su)
    print(ans)
"""

#2016_c
"""
while 1:
    m,n = map(int, input().split())
    if m == n == 0:
        break
    ma = 7368791
    d = [0]*(ma+1)
    z = m
    for i in range(n):
        while d[z]:
            z += 1
        j = z
        while j <= ma:
            d[j] = 1
            j += z
    for j in range(z,ma+1):
        if not d[j]:
            print(j)
            break
"""

#2018_c
"""
def factorize(n):
    if n < 4:
        return [1,n]
    i = 2
    l = [1]
    while i**2 <= n:
        if n%i == 0:
            l.append(i)
            if n//i != i:
                l.append(n//i)
        i += 1
    l.append(n)
    l.sort()
    return l
while 1:
    b = int(input())
    if b == 0:
        break
    f = factorize(2*b)
    for n in f[::-1]:
        a = 1-n+(2*b)//n
        if a >= 1 and a%2 == 0:
            print(a//2,n)
            break
"""

#2010_c
"""
import sys
dp = [100]*1000000
dp_2 = [100]*1000000
dp[0] = 0
dp_2[0] = 0
for i in range(1,181):
    s = i*(i+1)*(i+2)//6
    for j in range(s,1000000):
        if dp[j-s]+1 < dp[j]:
            dp[j] = dp[j-s]+1
    if s%2:
        for j in range(s,1000000):
            if dp_2[j-s]+1 < dp_2[j]:
                dp_2[j] = dp_2[j-s]+1
while 1:
    m = int(sys.stdin.readline())
    if m == 0:
        break
    print(dp[m],dp_2[m])
"""

#2015_c
"""
from collections import deque
while 1:
    n = int(input())
    if n == 0:
        break
    s = [input() for i in range(n)]
    d = [s[i].count(".") for i in range(n)]
    m = max(d)
    c = [s[i][-1] for i in range(n)]
    q = deque()
    for i in range(1,m+1)[::-1]:
        j = 0
        while j < n:
            for k in range(j,n):
                if d[k] == i:break
            else:
                break
            j = k
            op = c[j-1]
            while j < n and d[j] == i:
                q.append(j)
                j += 1
            j = k
            if op == "+":
                k = 0
                while q:
                    x = q.pop()
                    k += int(c[x])
                    c.pop(x)
                    d.pop(x)
                    n -= 1
            else:
                k = 1
                while q:
                    x = q.pop()
                    k *= int(c[x])
                    c.pop(x)
                    d.pop(x)
                    n -= 1
            c[j-1] = k
    print(c[0])
"""

#2013_c
"""
from collections import defaultdict

def parse_expr(s,i):
    i += 1
    if s[i] == "[":
        q = []
        while s[i] != "]":
            e,i = parse_expr(s,i)
            q.append(e)
        return (calc(q),i+1)
    else:
        n,i = parse_num(s,i)
        return (calc([n]),i+1)

def parse_num(s,i):
    m = int(s[i])
    i += 1
    while f_num[s[i]]:
        m *= 10
        m += int(s[i])
        i += 1
    return (m,i)

def calc(q):
    if len(q) == 1:
        return (q[0]+1)//2
    q.sort()
    return sum(q[:len(q)//2+1])

f_num = defaultdict(lambda : 0)
for i in range(10):
    f_num[str(i)] = 1

n = int(input())
for i in range(n):
    s = input()
    print(parse_expr(s,0)[0])
"""

#2003_C
while 1:
    w,h = LI()
    if w == h == 0:
        break
    s = SR(h)
    dp = [[0]*w for i in range(h)]
    for y in range(h):
        for x in range(w):
            if s[y][x].isdecimal():
                dp[y][x] = max(dp[y-1][x],dp[y][x-1])*10+int(s[y][x])
    ans = 0
    for i in dp:
        ans = max(ans,max(i))
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def isdigit(x):
    return '0' <= x <= '9'


def solve():
    W, H = map(int, input().split())
    if W == 0:
        exit()
    grid = [[v for v in input()[:-1]] for _ in range(H)]
    dp = [[-1]*W for _ in range(H)]

    max_val = 0
    for row in range(H):
        for col in range(W):
            if isdigit(grid[row][col]):
                if row > 0 and col > 0:
                    cand = max(dp[row-1][col], dp[row][col-1], 0)
                elif row == 0 and col == 0:
                    cand = 0
                elif row == 0:
                    cand = max(dp[row][col-1], 0)
                elif col == 0:
                    cand = max(dp[row-1][col], 0)

                dp[row][col] = cand*10+int(grid[row][col])

                max_val = max(max_val, dp[row][col])

    print(max_val)


while True:
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
def check(a,b):
    if (a,b) in memo:
        return memo[(a,b)]
    if 0<=a<h and 0<=b<w and field[a][b].isdigit():
        x=check(a+1,b)
        y=check(a,b+1)
        memo[(a,b)]=field[a][b]+(x if len(x)>len(y) else x if len(x)==len(y) and len(x)!=0 and int(x)>int(y) else y)
        return field[a][b]+(x if len(x)>len(y) else x if len(x)==len(y) and len(x)!=0 and int(x)>int(y) else y)
    else:
        return ''
while 1:
    w,h=map(int,input().split())
    if w==0:
        break
    field=[]
    for i in range(h):
        field.append(list(input()))
    ans='0'
    memo={}
    for i in range(h):
        for j in range(w):
            if field[i][j]!='0' and field[i][j].isdigit():
                tmp=check(i,j)
                if int(ans)<int(tmp):
                    ans=tmp
    print(ans)