fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int findMinCost(int **grid,int row,int col,int** dp,int r=0, int c=0)
  5. {
  6.  
  7.  
  8.      if(r >=row || c >=col)
  9.          return INT_MAX;
  10.  
  11.      if(r == row-1 && c == col-1)
  12.         return 1;
  13.  
  14.      if(dp[r][c] != -1)
  15.         return dp[r][c];
  16.  
  17.  
  18.      int right =  findMinCost(grid,row,col,dp,r,c+1);
  19.      int down  =  findMinCost(grid,row,col,dp,r+1,c);
  20.  
  21.  
  22.      if(right != INT_MAX)
  23.          right -= grid[r][c+1];
  24.  
  25.       if(down !=INT_MAX)
  26.           down -= grid[r+1][c];
  27.  
  28.     if(right<1)
  29.         right = 1;    
  30.     if(down<1)
  31.         down = 1;
  32.  
  33.      int mincost= min(right,down);
  34.      //  cout<<r<<" "<<c<<" "<<mincost<<endl;
  35.  
  36.  
  37.           dp[r][c]=mincost;
  38.  
  39.         return dp[r][c];
  40.  
  41. }
  42. int find(int **grid,int r,int c)
  43. {
  44.     int **dp= new int*[r];
  45.  
  46.       for(int i=0;i<r;i++)
  47.             dp[i]= new int[c];
  48.  
  49.        for(int i=0;i<r;i++)
  50.           for(int j=0;j<c;j++)
  51.              dp[i][j]=-1;
  52.  
  53.     int ans=findMinCost(grid,r,c,dp);
  54.  
  55.     for(int i=0;i<r;i++)
  56.            delete [] dp[i];
  57.         delete [] dp;
  58.  
  59.    return ans;
  60. }
  61.  
  62. int main()
  63. {
  64.  
  65.     int t;
  66.     cin>>t;
  67.     while(t--)
  68.     {
  69.        int r,c;
  70.         cin>>r>>c;
  71.         int **grid= new int* [r];
  72.  
  73.         for(int i=0;i<r;i++)
  74.             grid[i]= new int[c];
  75.  
  76.       for(int i=0;i<r;i++)
  77.           for(int j=0;j<c;j++)
  78.              cin>> grid[i][j];                
  79.  
  80.         cout<<find(grid,r,c)<<endl;
  81.  
  82.         for(int i=0;i<r;i++)
  83.            delete [] grid[i];
  84.         delete [] grid;
  85.  
  86.     }
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jid8mG
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!