CCT B6 - Right Down the Grid

You are in a 2D maze of dimensions N x M. Your initial position is (1,1) and your final position is (N,M).

The cell(i,j) has value A[i][j]. The cost of travelling any path in this maze is equal to the sum of values of all cells that you have visited while travelling the path.

From a cell (i,j) you can only go either right, or down, i.e. you can only go to (i + 1, j) or (i, j + 1). Note that at any point you cannot leave the grid.

Your task is to calculate the minimum cost that it would take you to go from the initial position to the final position.

Input

First line contains two integers N and M. Next N lines each contain M integers denoting the values of A[i][j]

Output

Print the minimum cost of travel

Notes

All input values do not exceed 1000

Sample Input 0

3 3
1 1 2
2 3 1
2 2 1

Sample Output 0

6

Solution :

#include <bits/stdc++.h>

using namespace std;

#define F(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)

#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)

int main()

{

    int X,Y; 

    cin>>X>>Y;

    int Cost[X][Y];

    F(i,0,X-1)

    {

        F(j,0,Y-1)

        {

            cin>>Cost[i][j];

        }

    }

    int MinCost[X][Y]; 

    MinCost[0][0] = Cost[0][0];

    F(j,1,Y-1)

        MinCost[0][j] = MinCost[0][j-1] + Cost[0][j];

    F(i,1,X-1)

        MinCost[i][0] = MinCost[i-1][0] + Cost[i][0];

    F(i,1,X-1)

    {

        F(j,1,Y-1)

        {

            MinCost[i][j] = min(MinCost[i-1][j],MinCost[i][j-1]) + Cost[i][j];

        }

    }

    cout<<MinCost[X-1][Y-1];

    return 0;

}