In NxN matrix containing numbers and block ‘x’.find the number of path from the source ‘s’ to destination ‘d’ which adds upto given sum ‘k’. Use Dynamic programming to solve this.Move in down ,right and diagonal direction.
input:
k = 3
s 1 1
1 x 1
1 1 d
output = 2
k = 5
e 1 1 1
1 1 1 1
1 1 1 1
1 1 1 s
output = 20
k = 7
e 2 3
2 x 2
1 2 s