#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int solve(vector<vector<int>>grid,int i,int j,int r,int c,int coins,vector<vector<vector<int>>>&dp)

{

if(coins<0 || i>r ||j>c ||i<0 ||j<0)

{

return 100000;

}

if(i==r and j==c)

{

return 0;

}

if(dp[i][j][coins]!=-1)

{

return dp[i][j][coins];

}

int right=1+solve(grid,i,j+1,r,c,coins-grid[i][j],dp);

int down=1+solve(grid,i+1,j,r,c,coins-grid[i][j],dp);

return dp[i][j][coins]=min(right,down);

}

int main()

{

vector<vector<int>>grid{

{0, 0 ,1},

{1, 0 ,1},

{1 ,0, 1},

{0 ,1, 0},

{0, 0 ,0}

};

int r=4,c=2;

int coins=1;

vector<vector<vector<int>>>dp(grid.size()+1,vector<vector<int>>(grid[0].size()+1,vector<int>(coins+1,-1)));

cout<<solve(grid,0,0,r,c,coins,dp);//it it returs a bigger value it meanns no path exist

}