Jozef

In [50]:
n,m,kvet = [int(_) for _ in input().split()]
luka = [[c for c in input()] for _ in range(n)]
print(*luka)

4 9 3
^...1#...
......1..
........1
........$
['^', '.', '.', '.', '1', '#', '.', '.', '.'] ['.', '.', '.', '.', '.', '.', '1', '.', '.'] ['.', '.', '.', '.', '.', '.', '.', '.', '1'] ['.', '.', '.', '.', '.', '.', '.', '.', '$']
In [60]:
max_k = kvet
k = kvet
pm = [[[0 for k in range(1+max_k)] for j in range(m+1)] for i in range(n+1)]
print(*pm)

[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
In [76]:
%%time
for i in range(1,n+1):
    for j in range(1,m+1):
        for k in range(1+max_k):
            if luka[i-1][j-1] == '^':
                pm[i][j][k] = 1 if k == 0 else 0
            elif luka[i-1][j-1] in ['.','$']: #prazdne/cielove policko
                pm[i][j][k] = sum([pm[i-1][j][k], pm[i][j-1][k], pm[i-1][j-1][k]]) #tri mozne smery                
            elif luka[i-1][j-1] == '#':
                pm[i][j][k] = 0
            else: 
                predch_k = k-int(luka[i-1][j-1])
                if predch_k >= 0:
                    pm[i][j][k] = sum([pm[i-1][j][predch_k], pm[i][j-1][predch_k], pm[i-1][j-1][predch_k]])
                    

Wall time: 0 ns
In [62]:
print(pm[n][m][k])

10
In [63]:
for i in range(n+1):
    print(*pm[i])

[0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]
[0, 0, 0, 0] [1, 0, 0, 0] [1, 0, 0, 0] [1, 0, 0, 0] [1, 0, 0, 0] [0, 1, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]
[0, 0, 0, 0] [1, 0, 0, 0] [3, 0, 0, 0] [5, 0, 0, 0] [7, 0, 0, 0] [8, 1, 0, 0] [8, 2, 0, 0] [0, 8, 2, 0] [0, 8, 2, 0] [0, 8, 2, 0]
[0, 0, 0, 0] [1, 0, 0, 0] [5, 0, 0, 0] [13, 0, 0, 0] [25, 0, 0, 0] [40, 1, 0, 0] [56, 4, 0, 0] [64, 14, 2, 0] [64, 30, 6, 0] [0, 64, 46, 10]
[0, 0, 0, 0] [1, 0, 0, 0] [7, 0, 0, 0] [25, 0, 0, 0] [63, 0, 0, 0] [128, 1, 0, 0] [224, 6, 0, 0] [344, 24, 2, 0] [472, 68, 10, 0] [536, 162, 62, 10]
In [77]:
%%time
pm = [[[-1 for k in range(1+max_k)] for j in range(m+1)] for i in range(n+1)]

def vyp_pm(i,j,k):
    if i == 0 or j == 0:
        pm[i][j][k] = 0
    elif i == 1 and j == 1:
        pm[i][j][k] = 1 if k == 0 else 0
    if pm[i][j][k] == -1:
        if luka[i-1][j-1] == '^':
                pm[i][j][k] = 1 if k == 0 else 0
        elif luka[i-1][j-1] in ['.','$']: #prazdne/cielove policko
                pm[i][j][k] = sum([vyp_pm(i-1,j,k), vyp_pm(i,j-1,k), vyp_pm(i-1,j-1,k)]) #tri mozne smery                
        elif luka[i-1][j-1] == '#':
                pm[i][j][k] = 0
        else: 
                predch_k = k-int(luka[i-1][j-1])
                if predch_k >= 0:
                    pm[i][j][k] = sum([vyp_pm(i-1,j,predch_k),vyp_pm(i,j-1,predch_k),vyp_pm(i-1,j-1,predch_k)])
                else:
                    pm[i][j][k] = 0
    return pm[i][j][k]

print(vyp_pm(n,m,kvet))

10
Wall time: 0 ns
In [ ]: