# solution works in O(m*n*N) with O(mxn) space

• class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<vector < int > > > vec (m,vector<vector < int > > (n,vector< int >(N+1,0)));
vector<vector <int > > vect (m,vector<int>(n,0));
int x=1000000007;
if(m==1 and n==1){vect[m-1][n-1]=4;}
if(m==1 and n>1) for(int e=1;e<=n-1;e++){vect[0][0]=3;vect[0][e]=2;vect[0][n-1]=3;}
if(n==1 and m>1) for(int e=1;e<=m-1;e++){vect[0][0]=3;vect[e][0]=2;vect[m-1][0]=3;}
// if(m==2 and n==2)
else if(m>1 and n>1 ){

``````        for(int l=1;l<m;l++)
{
vect[l][0]=1;
vect[l][n-1]=1;

}
for(int l=1;l<n;l++)
{
vect[0][l]=1;
vect[m-1][l]=1;

}
vect[0][0]=2;
vect[m-1][n-1]=2;
vect[0][n-1]=2;
vect[m-1][0]=2;
}

for(int a=0;a<N;a++)
{
for(int b=0;b<m;b++)
{
for(int c=0;c<n;c++)
{
if(a==0)
{ vec[b][c][a]=vect[b][c];}
if(a>0){
vec[b][c][a]=vect[b][c];
if(b-1>=0){vec[b][c][a]=((vec[b][c][a]%x)+(vec[b-1][c][a-1]%x))%x;}
if(c-1>=0){vec[b][c][a]=((vec[b][c][a]%x)+(vec[b][c-1][a-1]%x))%x;}
if(b+1<=m-1){vec[b][c][a]=((vec[b][c][a]%x)+(vec[b+1][c][a-1]%x))%x;}
if(c+1<=n-1){vec[b][c][a]=((vec[b][c][a]%x)+(vec[b][c+1][a-1]%x))%x;}
}
}
}

}
//for(int a=0;a<m;a++){for(int b=0;b<n;b++){cout<<vect[a][b]<<" ";}cout<<"\n ";}
if(N==0) return 0;
if(N==1){return vect[i][j];}
else
{
return vec[i][j][N-1];

}
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.