我比較暴力一點
直接在外面多弄一圈
然後每次都用備用陣列看下一步能走到哪裡
然後同時把外面那圈加起來就是答案
我感覺明天要hard了
嗚嗚嗚哇哇哇哇哇哇
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn)
{
vector<vector<long long>> paper(m+2 ,vector<long long>(n+2 , 0));
vector<vector<long long>> paper2(m+2 ,vector<long long>(n+2 , 0));
paper[startRow+1][startColumn+1] = 1;
long long pans = 0;
for(int r = 0 ; r < maxMove ; r ++)
{
for(int i = 0 ; i <= m+1 ; i ++)
{
for(int j = 0 ; j <= n+1 ; j ++)
{
paper2[i][j] = 0;
}
}
for(int i = 1 ; i <= m ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
long long k = paper[i][j];
k = k % 1000000007;
paper2[i-1][j] += k;
paper2[i+1][j] += k;
paper2[i][j-1] += k;
paper2[i][j+1] += k;
}
}
for(int i = 0 ; i <= m+1 ; i ++)
{
pans += paper2[i][0];
pans = pans % 1000000007;
pans += paper2[i][n+1];
pans = pans % 1000000007;
}
for(int i = 0 ; i <= n+1 ; i ++)
{
pans += paper2[0][i];
pans = pans % 1000000007;
pans += paper2[m+1][i];
pans = pans % 1000000007;
}
// for(int i = 0 ; i <= m+1 ; i ++)
// {
// for(int j = 0 ; j <= n+1 ; j ++)
// {
// printf("%d ",paper2[i][j]);
// }
// printf("\n");
// }
// printf("========\n");
paper = paper2;
}
int ans = pans % 1000000007;
return ans;
}
};