MISERMAN  Wise And Miser
Jack is a wise and miser man. Always tries to save his money.
One day, he wants to go from city A to city B. Between A and B, there are N number of cities(including B and excluding A) and in each city there are M buses numbered from 1 to M. And the fare of each bus is different. Means for all N*M busses, fare (K) may be different or same. Now Jack has to go from city A to city B following these conditions:
 At every city, he has to change the bus.
 And he can switch to only those buses which have number either equal or 1 less or 1 greater to the previous.
You are to help Jack to go from A to B by spending the minimum amount of money.
N, M, K <= 100.
Input
Line 1: N M
Line 2: NxM Grid
Each row lists the fares the M busses to go form the current city to the next city.
Output
Single Line containing the minimum amount of fare that Jack has to give.
Example
Input: 5 5 1 3 1 2 6 10 2 5 4 15 10 9 6 7 1 2 7 1 5 3 8 2 6 1 9 Output: 10
Explanation
1 > 4 > 1 > 3 > 1: 10
hide comments
apoorva222g:
20200126 11:05:06
easy dp problem of 2d array


dhj:
20200121 14:36:42
getting back to spoj after 3 years and getting an AC in a go is an amazing feeling 

harry_shit:
20191114 20:45:55
ac in one go after ages, simple dp :) 

zsumon:
20190730 03:21:10
weak dataset! 

scolar_fuad:
20190707 15:59:42
Simple dp used top up approach with memorization 

duke_knight:
20190624 08:25:16
AC in 1 go!! 

soub5184:
20190216 14:36:22
Submitted in java.AC in one go.


ashimk:
20190107 20:55:56
Recursion + Memoization did it for me :)


amvi:
20181108 11:34:18
no dp only recursion 

itssanat:
20181026 22:02:45
AC in one go :):) !!!! 
Added by:  The quick brown fox jumps over the lazy dog 
Date:  20101018 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC VB.NET 
Resource:  Udit Agarwal 