Algorithm
problem link- https://www.spoj.com/problems/MISERMAN/
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: N×M 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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
using namespace std;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int a[n+2][m+2];
memset(a,11,sizeof(a));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int k;
scanf("%d",&k);
if(i==1)
{
a[i][j]=k;
continue;
}
a[i][j]=min(min((k+a[i-1][j-1]),(k+a[i-1][j])),(k+a[i-1][j+1]));
}
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",a[i][j]);
}
cout<<endl;
}*/
int minifare=100000;
for(int i=0;i<m;i++){
if(a[n][i]<minifare)minifare=a[n][i];
}
printf("%d\n",minifare);
return 0;
}Input
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
Demonstration
SPOJ Solution-MISERMAN Wise And Miser-Solution in C, C++, Java, Python