递归会超时,用递推做
@[xiayunpeng](/user/767465)
代码如下:
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n, m, p, q,a[25][25];
int dp[25][25];
bool vis[25][25];
int hx[8]={1,1,-1,-1,2,2,-2,-2},hy[8]={2,-2,2,-2,1,-1,1,-1};
int f(int x,int y) {
// if(x==1||y==1)return 1;
// else if(a[x][y]==-1)return 0;
for (int i = 1; i <= x; i++)
{
for (int j = 1; j <= y; j++)
{
if (vis[i][j])
dp[i][j] = 0;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
// cout << "\t" << a[i][j];
}
// cout << endl;
}
return dp[x][y];
// return f(x-1,y)+f(x,y-1);
}
int main() {
// ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> p >> q;
vis[p][q] = true;
// n++,m++,p++,q++;
for (int i = 0; i < 8; i++) {
vis[p+hx[i]][q+hy[i]] = true;
}
// dp数组初始化
int li = 0, lj = 0;
while (li <= m && !vis[0][li])
{
dp[0][li++] = 1;
}
while (lj <= n && !vis[lj][0])
{
dp[lj++][0] = 1;
}
dp[p][q]=-1;
cout << f(n, m);
return 0;
}
```
更改了很多,不知道能不能AC,不过样例过了
by 2058_lunar_fall @ 2023-04-02 19:33:04
谢谢
by xiayunpeng @ 2023-05-17 19:46:40