# Easy understand c++ 9ms using 2*m*n space with explaination

• table[i][j] is the path number of rolling k steps for cell (i,j). next[i][j] is the path number of rolling k+1 steps for cell(i,j). hence next[i][j]=table[i-1][j]+table[i][j-1]+table[i+1][j]+table[i][j+1]. If only roll 1 steps, only boundary cell has value. initialize it at beginning.

``````class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<size_t>> table(m, vector<size_t>(n, 0));

size_t ans=0;

for(int k=1; k<=N; k++)
{
vector<vector<size_t>> next(m, vector<size_t>(n, 0));
if(k==1)
{
for(int x=0; x<m; x++)
{
for(int y=0; y<n; y++)
{
if(x==0)
++table[x][y];
if(y==0)
++table[x][y];
if(y==n-1)
++table[x][y];
if(x==m-1)
++table[x][y];

}
}
}
else
{
for(int x=0; x<m; x++)
{
for(int y=0; y<n; y++)
{
size_t val=0;

val+=(x==0?0:table[x-1][y]);

val+=(y==0?0:table[x][y-1]);

val+=(x==m-1?0:table[x+1][y]);

val+=(y==n-1?0:table[x][y+1]);
next[x][y]=val%mod;
}
}
table=next;
}
ans=(ans+table[i][j])%mod;
}
return ans;
}

private:
const int mod=1e9+7;
};
``````

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