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: Wrong Answer

Solution code:
while 1:
	W, H = map(int,raw_input().split(" "))
	if W == H == 0: 
		break
	field = [[c for c in raw_input()] for _ in range(H)]
	secret = [0, ""]
	for j in range(H):
		for i in range(W):
			if not (field[j][i].isdigit() and field[j][i] != "0"):
				continue
			pre = left = top = ""
			if i > 0 and field[j][i-1].isdigit() and field[j][i-1] != "0":
				left = field[j][i-1]
			if j > 0 and field[j-1][i].isdigit() and field[j-1][i] != "0":
				top = field[j-1][i]
			if len(left) == len(top):
				pre = left if left > top else top
			else :
				pre = left if len(left) > len(top) else top
			field[j][i] = pre + field[j][i]
			length = len(field[j][i])
			if length > secret[0]:
				secret[1] = field[j][i]
				secret[0] = length
			elif length == secret[0] and field[j][i] < secret[1]:
				secret[1] = field[j][i]
	print secret[1]

Submission status: Wrong Answer

Solution code:
while 1:
	W, H = map(int,raw_input().split(" "))
	if W == H == 0: 
		break
	field = [[c for c in raw_input()] for _ in range(H)]
	secret = [0, ""]
	for j in range(H):
		for i in range(W):
			if not field[j][i].isdigit():
				continue
			pre = left = top = ""
			if i > 0 and field[j][i-1].isdigit() and field[j][i-1] != "0":
				left = field[j][i-1]
			if j > 0 and field[j-1][i].isdigit() and field[j-1][i] != "0":
				top = field[j-1][i]
			if len(left) == len(top):
				pre = left if left > top else top
			else :
				pre = left if len(left) > len(top) else top
			field[j][i] = pre + field[j][i]
			length = len(field[j][i])
			if length > secret[0]:
				secret[1] = field[j][i]
				secret[0] = length
			elif length == secret[0] and field[j][i] < secret[1]:
				secret[1] = field[j][i]
	print secret[1]

Submission status: Wrong Answer

Solution code:
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    
    dp = [["0"]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                if w > 0: dp[h][w] = str(max(int(dp[h][w]),int(dp[h][w-1]+C[h][w])))
                if h > 0: dp[h][w] = str(max(int(dp[h][w]),int(dp[h-1][w]+C[h][w])))
                ans = max(ans, int(dp[h][w]))
    print ans

Submission status: Wrong Answer

Solution code:
def solve():
    global Map, w, h
    dp=[['']*w]*h
    res=''

    def nozero(st):
        return st.lstrip('0')

    #whats the difference from max(str1,str2)??
    def maxs(s1, s2):
        if len(s1) > len(s2): return s1
        elif len(s1) < len(s2): return s2
 
        if s1 > s2: return s1
        else: return s2

    for i in range(h):
        for j in range(w):
            if(Map[i][j].isalpha()):continue
            '''
                if(0<=i-1<h and (Map[i-1][x].isdigit() and  dp[i-1][j]) and (0<=j-1<w and Map[i][j-1].isdigit() and dp[i][j-1])):
                    tmp1=dp[i-1][j]+Map[i][j]
                    tmp2=dp[i][j-1]+Map[i][j]
                    dp[i][j]=max(tmp1,tmp2)

                    res=max(res,dp[i][j])
                    continue
            '''
            if(0<=j-1<w):
                dp[i][j]=maxs(dp[i][j-1],dp[i][j])
                    

            if(0<=i-1<h):
                dp[i][j]=maxs(dp[i-1][j],dp[i][j])
                    
            dp[i][j]+=Map[i][j]
            if ('0' in dp[i][j]):dp[i][j]=nozero(dp[i][j])
            res=maxs(res,dp[i][j])

    return res

while(True):
    Map=[]
    w,h=map(int,raw_input().split(' '))
    if (w==0 and h==0):break
    for i in range(h):
        Map.append(list(raw_input()))

    print solve()

Submission status: Wrong Answer

Solution code:
def solve():
    global Map, w, h
    dp=[['']*w]*h
    res=''

    def nozero(st):
        return st.lstrip('0')

    #whats the difference from max(str1,str2)??
    def maxs(s1, s2):
        if len(s1) > len(s2): return s1
        elif len(s1) < len(s2): return s2
 
        if s1 > s2: return s1
        else: return s2

    for i in range(h):
        for j in range(w):
            if(Map[i][j].isalpha()):continue
            '''
                if(0<=i-1<h and (Map[i-1][x].isdigit() and  dp[i-1][j]) and (0<=j-1<w and Map[i][j-1].isdigit() and dp[i][j-1])):
                    tmp1=dp[i-1][j]+Map[i][j]
                    tmp2=dp[i][j-1]+Map[i][j]
                    dp[i][j]=max(tmp1,tmp2)

                    res=max(res,dp[i][j])
                    continue
            '''
            if(0<j):
                dp[i][j]=maxs(dp[i][j-1],dp[i][j])
                    

            if(0<i):
                dp[i][j]=maxs(dp[i-1][j],dp[i][j])
                    
            dp[i][j]+=Map[i][j]
            if ('0' in dp[i][j]):dp[i][j]=nozero(dp[i][j])
            res=maxs(res,dp[i][j])

    return res

while(True):
    Map=[]
    w,h=map(int,raw_input().split(' '))
    if (w==0 and h==0):break
    for i in range(h):
        Map.append(list(raw_input()))

    print solve()

Submission status: Wrong Answer

Solution code:
def solve():
    global Map, w, h
    dp=[['']*w]*h
    res=''

    def nozero(st):
        return st.lstrip('0')

    #whats the difference from max(str1,str2)??
    def maxs(s1, s2):
        if len(s1) > len(s2): return s1
        elif len(s1) < len(s2): return s2
 
        if s1 > s2: return s1
        else: return s2

    for i in range(h):
        for j in range(w):
            if(Map[i][j].isalpha()):continue
            '''
                if(0<=i-1<h and (Map[i-1][x].isdigit() and  dp[i-1][j]) and (0<=j-1<w and Map[i][j-1].isdigit() and dp[i][j-1])):
                    tmp1=dp[i-1][j]+Map[i][j]
                    tmp2=dp[i][j-1]+Map[i][j]
                    dp[i][j]=max(tmp1,tmp2)

                    res=max(res,dp[i][j])
                    continue
            '''
            if(0<j):
                dp[i][j]=maxs(dp[i][j-1],dp[i][j])
                    

            if(0<i):
                dp[i][j]=maxs(dp[i-1][j],dp[i][j])
                    
            dp[i][j]+=Map[i][j]
            #if ('0' in dp[i][j]):dp[i][j]=nozero(dp[i][j])
            if(dp[i][j] is '0'):dp[i][j]=''
            res=maxs(res,dp[i][j])

    return res

while(True):
    Map=[]
    w,h=map(int,raw_input().split(' '))
    if (w==0 and h==0):break
    for i in range(h):
        Map.append(list(raw_input()))

    print solve()

Submission status: Wrong Answer

Solution code:
def solve():
    global Map, w, h
    dp=[['']*w]*h
    res=''

    def nozero(st):
        return st.lstrip('0')

    #whats the difference from max(str1,str2)??
    def maxs(s1, s2):
        if len(s1) > len(s2): return s1
        elif len(s1) < len(s2): return s2
 
        if s1 > s2: return s1
        else: return s2

    for i in range(h):
        for j in range(w):
            if(Map[i][j].isalpha()):continue

            if(0<j):
                dp[i][j]=maxs(dp[i][j-1],dp[i][j])
                    

            if(0<i):
                dp[i][j]=maxs(dp[i-1][j],dp[i][j])
                    
            dp[i][j]+=Map[i][j]
            #if ('0' in dp[i][j]):dp[i][j]=nozero(dp[i][j])
            if(dp[i][j] is '0'):dp[i][j]=''
            res=maxs(res,dp[i][j])

    return res

while(True):
    Map=[]
    w,h=map(int,raw_input().split(' '))
    if (w==0 and h==0):break
    for i in range(h):
        Map.append(list(raw_input()))

    print solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def recursion(y, x, island, dp):
    if island[y][x].isdigit() and int(island[y][x]) in range(10):        
        if y == 0 and x == 0:
            dp[y][x] = int(island[y][x])
        elif y == 0:
            if dp[y][x-1] != -1:
                dp[y][x] = dp[y][x-1] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        elif x == 0:
            if dp[y-1][x] != -1:
                dp[y][x] = dp[y-1][x] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        else:
            dp[y][x] = max(dp[y][x-1] * 10 + int(island[y][x]), dp[y-1][x] * 10 + int(island[y][x]))
    else:
        dp[y][x] = -1
        
def solve(w, h, island, dp):
    for i in range(h):
        for j in range(w):
            recursion(i, j, island, dp)
    print max(map(max, dp))

def func():
    '''

    '''
    while True:
        global count
        w, h = map(int, raw_input().split())

        if w == 0 and h == 0:
            break

        island = []
        count = 0
        for i in range(h):
            row = []
            line = raw_input()
            for j in line:
                row.append(j)
            island.append(row)
        
        dp = []
        for i in range(h):
            dp_row = []
            for j in range(w):
                dp_row.append(0)
            dp.append(dp_row)
        solve(w, h, island, dp)


func()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def recursion(y, x, island, dp):
    if island[y][x].isdigit() and int(island[y][x]) in range(10):        
        if y == 0 and x == 0:
            dp[y][x] = int(island[y][x])
        elif y == 0:
            if dp[y][x-1] != -1:
                dp[y][x] = dp[y][x-1] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        elif x == 0:
            if dp[y-1][x] != -1:
                dp[y][x] = dp[y-1][x] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        else:
            dp[y][x] = max(dp[y][x-1] * 10 + int(island[y][x]), dp[y-1][x] * 10 + int(island[y][x]))
    else:
        dp[y][x] = -1
        
def solve(w, h, island, dp):
    for i in range(h):
        for j in range(w):
            recursion(i, j, island, dp)
    print max(map(max, dp))

def func():
    '''

    '''
    while True:
        global count
        w, h = map(int, raw_input().split())

        if w == 0 and h == 0:
            break

        island = []
        count = 0
        for i in range(h):
            row = []
            line = raw_input()
            for j in line:
                row.append(j)
            island.append(row)
        
        dp = []
        for i in range(h):
            dp_row = []
            for j in range(w):
                dp_row.append(0)
            dp.append(dp_row)
        solve(w, h, island, dp)

if __name__ == '__main__':
    func()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def recursion(y, x, island, dp):
    if island[y][x].isdigit() and int(island[y][x]) in range(10):        
        if y == 0 and x == 0:
            dp[y][x] = int(island[y][x])
        elif y == 0:
            if dp[y][x-1] != -1:
                dp[y][x] = dp[y][x-1] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        elif x == 0:
            if dp[y-1][x] != -1:
                dp[y][x] = dp[y-1][x] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        else:
            if dp[y-1][x] == -1 and dp[y][x-1] == -1:
                dp[y][x] = int(island[y][x])
            elif dp[y-1][x] == -1:
                dp[y][x] = dp[y][x-1] * 10 + int(island[y][x])
            elif dp[y][x-1] == -1:
                dp[y][x] = dp[y-1][x] * 10 + int(island[y][x])
            else:
                dp[y][x] = max(dp[y][x-1] * 10 + int(island[y][x]), dp[y-1][x] * 10 + int(island[y][x]))
    else:
        dp[y][x] = -1
        
def solve(w, h, island, dp):
    for i in range(h):
        for j in range(w):
            recursion(i, j, island, dp)
    print dp
    print max(map(max, dp))

def func():
    '''

    '''
    while True:
        global count
        w, h = map(int, raw_input().split())

        if w == 0 and h == 0:
            break

        island = []
        count = 0
        for i in range(h):
            row = []
            line = raw_input()
            for j in line:
                row.append(j)
            island.append(row)
        
        dp = []
        for i in range(h):
            dp_row = []
            for j in range(w):
                dp_row.append(0)
            dp.append(dp_row)
        solve(w, h, island, dp)

if __name__ == '__main__':
    func()

Submission status: Time Limit Exceeded

Solution code:
def rec(h,w,s):
    res = 0
    for dh,dw in [[1,0],[0,1]]:
        nh,nw = h+dh,w+dw
        if 0 <= nh < H and 0 <= nw < W and C[nh][nw].isdigit():
            res = max(res, rec(nh,nw,s+C[nh][nw]))
    return res if res > 0 else int(s)

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
           if C[h][w].isdigit():
               ans = max(ans, rec(h,w,C[h][w]))
    print ans

Submission status: Time Limit Exceeded

Solution code:
def rec(h,w,s):
    res = 0
    for dh,dw in [[1,0],[0,1]]:
        nh,nw = h+dh,w+dw
        if 0 <= nh < H and 0 <= nw < W and C[nh][nw].isdigit():
            res = max(res, rec(nh,nw,s+C[nh][nw]))
    return res if res > 0 else int(s)

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
           if C[h][w].isdigit():
               if w > 0 and C[h][w-1].isdigit() or h > 0 and C[h-1][w].isdigit(): continue
               ans = max(ans, rec(h,w,C[h][w]))
    print ans

Submission status: Time Limit Exceeded

Solution code:
drc = [(0, 1), (1, 0)]


def dfs(r, c):
    ret = []
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if nr < H and nc < W and board[nr][nc].isdigit():
            cand = dfs(nr, nc)
            if len(cand) > len(ret) or (len(cand) == len(ret) and cand > ret):
                ret = cand
    return [board[r][c]] + ret


while True:
    W, H = map(int, input().split())
    if not (W | H):
        break
    board = [input() for _ in range(H)]
    ans = ''
    for r in range(H):
        for c in range(W):
            if board[r][c].isdigit() and board[r][c] != '0':
                cand = ''.join(dfs(r, c))
                # print(cand)
                if len(cand) > len(ans) or (len(cand) == len(ans) and cand > ans):
                    ans = cand
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
mv=((1,0),(0,1))

def dfs(x,y,ans):
    global res
    ans=max(ans,int(str(ans)+C[y][x]))
    res=max(ans,res)
    for dx,dy in mv:
        mx=x+dx
        my=y+dy
        if mx<0 or mx>=W or my<0 or my>=H:
            continue
        if C[my][mx].isdigit():
            dfs(mx,my,ans)

while True:
    W,H=map(int,raw_input().split())
    if W==H==0:break
    C=[raw_input() for i in range(H)]
    res=0
    for i in range(H):
        for j in range(W):
            if C[i][j].isdigit() and C[i][j]!="0":
                dfs(j,i,0)
    print res

Submission status: Accepted

Solution code:
# AOJ 1126: The Secret Number
# Python3 2018.7.16 bal4u

while True:
	W, H = map(int, input().split())
	if W == 0: break
	d = [list(input()) for r in range(H)]
	a = [[0 for c in range(W)] for r in range(H)]
	ans = 0
	for r in range(H):
		for c in range(W):
			if not d[r][c].isdigit(): continue
			a[r][c] = k = int(d[r][c])
			if c > 0 and d[r][c-1].isdigit():
				a[r][c] = a[r][c-1]*10 + k
			if r > 0 and d[r-1][c].isdigit():
				t = a[r-1][c]*10 + k
				a[r][c] = max(a[r][c], t)
			ans = max(ans, a[r][c])
	print(ans);

Submission status: Accepted

Solution code:
# AOJ 1126: The Secret Number
# Python3 2018.7.16 bal4u

while True:
	W, H = map(int, input().split())
	if W == 0: break
	d = [list(input()) for r in range(H)]
	a = [[0 for c in range(W)] for r in range(H)]
	ans = 0
	for r in range(H):
		for c in range(W):
			if d[r][c] >= '0' and d[r][c] <= '9':
				k = int(d[r][c])
				k1 = k2 = 0
				if c > 0: k1 = a[r][c-1]*10 + k
				if r > 0: k2 = a[r-1][c]*10 + k
				a[r][c] = max(k, k1, k2)
				ans = max(ans, a[r][c])
	print(ans);

Submission status: Accepted

Solution code:
while 1:
	W, H = map(int,raw_input().split(" "))
	if W == H == 0: 
		break
	field = [[c for c in raw_input()] for _ in range(H)]
	secret = [0, ""]
	for j in range(H):
		for i in range(W):
			if not field[j][i].isdigit():
				continue
			pre = left = top = ""
			if i > 0 and field[j][i-1].isdigit() and field[j][i-1] != "0":
				left = field[j][i-1]
			if j > 0 and field[j-1][i].isdigit() and field[j-1][i] != "0":
				top = field[j-1][i]
			if len(left) == len(top):
				pre = left if left > top else top
			else :
				pre = left if len(left) > len(top) else top
			field[j][i] = pre + field[j][i]
			length = len(field[j][i])
			if length > secret[0]:
				secret[1] = field[j][i]
				secret[0] = length
			elif length == secret[0] and field[j][i] > secret[1]:
				secret[1] = field[j][i]
	print secret[1]

Submission status: Accepted

Solution code:
while 1:
	W, H = map(int,raw_input().split(" "))
	if W == H == 0: 
		break
	field = [[c for c in raw_input()] for _ in range(H)]
	secret = [0, ""]
	for j in range(H):
		for i in range(W):
			if not field[j][i].isdigit():
				continue
			left = top = ""
			if i > 0 and field[j][i-1].isdigit() and field[j][i-1] != "0":
				left = field[j][i-1]
			if j > 0 and field[j-1][i].isdigit() and field[j-1][i] != "0":
				top = field[j-1][i]
			if len(left) == len(top):
				field[j][i] = (left if left > top else top) + field[j][i]
			else :
				field[j][i] = (left if len(left) > len(top) else top) + field[j][i]
			length = len(field[j][i])
			if length > secret[0]:
				secret[1] = field[j][i]
				secret[0] = length
			elif length == secret[0] and field[j][i] > secret[1]:
				secret[1] = field[j][i]
	print secret[1]

Submission status: Accepted

Solution code:
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    
    dp = [["0"]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                dp[h][w] = str(max(int(dp[h][w]),int(C[h][w])))
                if w > 0: dp[h][w] = str(max(int(dp[h][w]),int(dp[h][w-1]+C[h][w])))
                if h > 0: dp[h][w] = str(max(int(dp[h][w]),int(dp[h-1][w]+C[h][w])))
                ans = max(ans, int(dp[h][w]))
    print ans

Submission status: Accepted

Solution code:
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    dp = [[0]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                dp[h][w] = max(dp[h][w],int(C[h][w]))
                if w > 0: dp[h][w] = max(dp[h][w],int(str(dp[h][w-1])+C[h][w]))
                if h > 0: dp[h][w] = max(dp[h][w],int(str(dp[h-1][w])+C[h][w]))
                ans = max(ans,dp[h][w])
    print ans

Submission status: Accepted

Solution code:
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    dp = [[0]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                dp[h][w] = max(dp[h][w],int(C[h][w]))
                if w > 0: dp[h][w] = max(dp[h][w],int(str(dp[h][w-1])+C[h][w]))
                if h > 0: dp[h][w] = max(dp[h][w],int(str(dp[h-1][w])+C[h][w]))
    print max(max(i) for i in dp)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

while True:
    w, h = map(int, sys.stdin.readline().split( " " ) )
    if w == 0 and h == 0:
        break
    table = []
    for i in range(h):
        table.append( sys.stdin.readline() )

    dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
    for i in range( h ):
        for j in range( w ):
            if '0' <= table[ i ][ j ] <= '9' :
                val = ord( table[ i ][ j ] ) - ord( '0' )
                dp[ i + 1 ][ j + 1 ] = max( dp[ i ][ j + 1 ], dp[ i + 1 ][ j ] ) * 10 + val
    print max( [ max( dp[ i ] ) for i in range( h + 1 ) ] )

Submission status: Accepted

Solution code:
#whats the difference with max(st1,st2)
def maxs(s1, s2):
    if len(s1) > len(s2): return s1
    elif len(s1) < len(s2): return s2
        
    if s1 > s2: return s1
    else: return s2

def nozero(st):
    return st.lstrip('0')

while True:
    Map=[]
    w,h=map(int,raw_input().split(' '))
    if (w==0 and h==0):break
    for i in range(h):
        Map.append(raw_input())

    res=''
    #always init 2d list this way
    dp=[['' for __ in range(w)] for __ in range(h)]

    for i in range(h):
        for j in range(w):
            if(Map[i][j].isalpha()):
                continue

            if j>0:
                dp[i][j]=maxs(dp[i][j],dp[i][j-1])

            if i>0:
                dp[i][j]=maxs(dp[i][j],dp[i-1][j])
                    
            dp[i][j]+=Map[i][j]
            if ('0' in dp[i][j]):dp[i][j]=nozero(dp[i][j])
            if dp[i][j] is '0':dp[i][j]=''
            res=maxs(res,dp[i][j])


    print res

Submission status: Accepted

Solution code:
drc = [(0, 1), (1, 0)]


def dfs(r, c):
    if (r, c) in memo:
        return memo[r, c]
    ret = ''
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if nr < H and nc < W and board[nr][nc].isdigit():
            cand = dfs(nr, nc)
            if len(cand) > len(ret) or (len(cand) == len(ret) and cand > ret):
                ret = cand
    memo[r, c] = board[r][c] + ''.join(ret)
    return board[r][c] + ret


while True:
    W, H = map(int, input().split())
    if not (W | H):
        break
    board = [input() for _ in range(H)]
    memo = dict()
    ans = ''
    for r in range(H):
        for c in range(W):
            if board[r][c].isdigit() and board[r][c] != '0':
                cand = dfs(r, c)
                if len(cand) > len(ans) or (len(cand) == len(ans) and cand > ans):
                    ans = cand
    print(ans)

Submission status: Accepted

Solution code:
import string

def fun(x):
    for c in x:
        if c not in string.digits:
            return -1
    return int(x)

while(1):
    [W,H]=map(int, raw_input().split())
    if W==0: break
    A=[]
    for i in range(H):
        A.append(raw_input())
    B=[['a' for i in range(W+1)] for j in range(H+1)]
    ans=-1
    for p in range(2, H+2):
        for q in range(2, W+2):
            [j,k]=[-p,-q]
            C= map(lambda x: A[j+1][k+1]+x, ['', B[j+1][k] , B[j][k+1] ]    )
            D=sorted(sorted(C, key = lambda x: len(x) ), key= lambda x: fun(x)) [-1]
            if fun(D)!=-1:
                B[j][k]=D
                ans=max(ans,int(B[j][k]))
    print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        w,h = LI()
        if w == 0 and h == 0:
            break
        a = [[c for c in S()] for _ in range(h)]
        t = [[0]*w for i in range(h)]
        r = 0
        for i in range(h):
            for j in range(w):
                c = a[i][j]
                if not ('0' <= c <= '9'):
                    continue
                d = int(c) + t[i][j] * 10
                if r < d:
                    r = d
                if i < h-1 and t[i+1][j] < d:
                    t[i+1][j] = d
                if j < w-1 and t[i][j+1] < d:
                    t[i][j+1] = d
        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import sys

def maxs(s1, s2):
    if len(s1) > len(s2): return s1
    elif len(s1) < len(s2): return s2

    if s1 > s2: return s1
    else: return s2
    

while 1:
    w,h = map(int, raw_input().split())
    if not(w or h): break
    f = []
    for i in xrange(h):
        f.append(raw_input())

    ans = ''
    t = [['' for j in xrange(w)] for i in xrange(h)]
    for i in xrange(h):
        for j in xrange(w):
            if not(ord('0') <= ord(f[i][j]) <= ord('9')):
                continue
            if j>0: t[i][j] = maxs(t[i][j], t[i][j-1])
            if i>0: t[i][j] = maxs(t[i][j], t[i-1][j])
            t[i][j] += f[i][j]
            if t[i][j] is '0': t[i][j] = ''

            ans = maxs(ans, t[i][j])

    print ans

Submission status: Accepted

Solution code:
import sys
import collections

while True:
    W, H = map(int, sys.stdin.readline().split())
    if W == 0:
        break
    area = [[-10**80 for i in xrange(H + 2)] for j in xrange(W + 2)]
    result = -1
    for i in xrange(H):
        line = sys.stdin.readline().strip()
        for j in xrange(W):
            if '0' <= line[j] <= '9':
                area[j + 1][i + 1] = int(line[j])
    for i in xrange(H):
        for j in xrange(W):
            area[j + 1][i + 1] = max(area[j + 1][i + 1], area[j + 1][i + 1] + area[j + 1][i] * 10, area[j + 1][i + 1] + area[j][i + 1] * 10)
            result = max(result, area[j + 1][i + 1])
    print result

Submission status: Accepted

Solution code:
while True:
    W,H=map(int,raw_input().split())
    if W==H==0:break
    C=[raw_input() for i in range(H)]
    table=[[""]*W for i in range(H)]
    ans=0
    for y in range(H):
        for x in range(W):
            if C[y][x].isdigit():
                a,b,c=table[y-1][x],table[y][x-1],C[y][x]
                if a==b=="":
                    table[y][x]=c
                elif a=="":
                    table[y][x]=b+c
                elif b=="":
                    table[y][x]=a+c
                elif int(a)>=int(b):
                    table[y][x]=a+c
                elif int(a)<int(b):
                    table[y][x]=b+c
                ans=ans if ans>int(table[y][x]) else int(table[y][x])
    print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def recursion(y, x, island, dp):
    if island[y][x].isdigit() and int(island[y][x]) in range(10):        
        if y == 0 and x == 0:
            dp[y][x] = int(island[y][x])
        elif y == 0:
            if dp[y][x-1] != -1:
                dp[y][x] = dp[y][x-1] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        elif x == 0:
            if dp[y-1][x] != -1:
                dp[y][x] = dp[y-1][x] * 10 + int(island[y][x])
            else:
                dp[y][x] = int(island[y][x])
        else:
            if dp[y-1][x] == -1 and dp[y][x-1] == -1:
                dp[y][x] = int(island[y][x])
            elif dp[y-1][x] == -1:
                dp[y][x] = dp[y][x-1] * 10 + int(island[y][x])
            elif dp[y][x-1] == -1:
                dp[y][x] = dp[y-1][x] * 10 + int(island[y][x])
            else:
                dp[y][x] = max(dp[y][x-1] * 10 + int(island[y][x]), dp[y-1][x] * 10 + int(island[y][x]))
    else:
        dp[y][x] = -1
        
def solve(w, h, island, dp):
    for i in range(h):
        for j in range(w):
            recursion(i, j, island, dp)
    #print dp
    print max(map(max, dp))

def func():
    '''

    '''
    while True:
        global count
        w, h = map(int, raw_input().split())

        if w == 0 and h == 0:
            break

        island = []
        count = 0
        for i in range(h):
            row = []
            line = raw_input()
            for j in line:
                row.append(j)
            island.append(row)
        
        dp = []
        for i in range(h):
            dp_row = []
            for j in range(w):
                dp_row.append(0)
            dp.append(dp_row)
        solve(w, h, island, dp)

if __name__ == '__main__':
    func()

Submission status: Accepted

Solution code:
while True:
    w,h = map(int,input().split())
    if w == 0:
        break
    c = [input() for i in range(h)]
    dp = [[0]*w for i in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            d = ord(c[i][j]) - ord('0')
            if not (d>=0 and d<=9):
                continue
            dp[i][j] = d
            if i > 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j]*10+d)
            if j > 0:
                dp[i][j] = max(dp[i][j], dp[i][j-1]*10+d)
            ans = max(ans, dp[i][j])
    print(ans)