 CDW07-CODEWARS

Author: Vipul Jain
Tester: Abhishek Mishra
Editorial: Utkarsh Jaiswal

Difficulty:
Medium

Prerequisite:
Array , DP

Explanation & Algorithm:
Given a integer n and three matrix arr1[][] ,arr2[][],arr3[][] which contain the value of x,y and z for each cell respectively, write a function that returns the minimum cost to reach (m, n) from (0, 0.The total cost of a path to reach (m, n) is the sum of all the costs on that path . You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1), and (i+1, j+1) can be traversed.

For example, in the following figure, what is the minimum cost path to (2, 2)?

3
1 2 1
3 4 5
1 1 1

2 3 4
1 3 1
2 1 1

1 8 9
1 4 5
6 5 4

The path with minimum cost is (0, 0) - > (1, 0) - >(2, 1) - > (2, 2) .Cost of path is 2 + 1 + 1 is equal to 4.

Optimal sub-problem:
The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or (m, n-1).
If you reach (m, n) from (m-1,n-1) then total cost will be the cost of to reach (m-1, n-1) plus arr3[m-1, n-1].let this value be stored in variable a.
if you reach (m, n) from (m,n-1) then total cost will be the cost of to reach (m, n-1) plus arr1[m, n-1].let this value be stored in variable b.
If you reach (m, n) from (m-1,n) then total cost will be the cost of to reach (m-1, n) plus arr2[m-1, n].let this value be stored in variable c.
minCost(m, n) =min(min (a, b) , c) .

Approach:
If you solve this recursively then it will take exponential time and it shows the time limit exceeded error.
In the optimal approach we use a temporary matrix dp[][] in which at any cell (i, j) dp[I][j] store the minimum cost to reach (i, j) cell from (0, 0).
Below is the implementation of the approach.

Solution

Setter's Code

#include<bits/stdc++.h>

using namespace std;

int solve(int n,vector<vector> &arr1,vector<vector> &arr2,vector<vector> &arr3){

int dp[n][n]={};

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

if(i==0 && j==0){

dp=0;

}

else if(i==0){

dp[i][j]=dp[i][j-1]+arr1[i][j-1];

}

else if(j==0){

dp[i][j]=dp[i-1][j]+arr2[i-1][j];

}

else{

int a=dp[i-1][j]+arr2[i-1][j];

int b=dp[i][j-1]+arr1[i][j-1];

int c=dp[i-1][j-1]+arr3[i-1][j-1];

dp[i][j]=min(min(a,b),c);

}

}

}

return dp[n-1][n-1];

}

int main(){

int n;

cin>>n;

vector<vector<int>> arr1(n,vector<int>(n));

vector<vector<int>> arr2(n,vector<int>(n));

vector<vector<int>> arr3(n,vector<int>(n));

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

cin>>arr1[i][j];

}

}

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

cin>>arr2[i][j];

}

}

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

cin>>arr3[i][j];

}

}

cout<<solve(n,arr1,arr2,arr3)<<endl;

return 0;

}

Tester's Code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

void solve() {
ll n; cin >> n;
vector<vector> x(n, vector(n)), y(n, vector(n)), z(n, vector(n)), dp(n, vector(n, 0));
for (auto &r : x) {
for (auto &c : r) cin >> c;
}
for (auto &r : y) {
for (auto &c : r) cin >> c;
}
for (auto &r : z) {
for (auto &c : r) cin >> c;
}
for (ll j = 1; j < n; j++) {

dp[j] = dp[j - 1] + x[j - 1];
}
for (ll i = 1; i < n; i++) {

dp[i] = dp[i - 1] + y[i - 1];
}

dp = 0;
for (ll i = 1; i < n; i++) {
for (ll j = 1; j < n; j++) {
dp[i][j] = min({dp[i - 1][j] + y[i - 1][j], dp[i][j - 1] + x[i][j - 1], dp[i - 1][j - 1] + z[i - 1][j - 1]});

}
}

cout << dp[n - 1][n - 1] << "\n";

}

int main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int tc = 1;

while (tc--) {
solve();
}

return 0;

}