问5 跳马问题变种【骑士游历问题】超时了
2024-03-30 16:24:24
发布于：广东
40阅读
0回复
0点赞
【问题5】呜呜呜呜呜呜此题我超时了，只得了60分，你们可以帮我看看哪错了吗？
（嘀咕：我明明用记忆化了呀。。。。。。。。💔）
【递归算法】【搜索与回溯算法】骑士游历问题
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如图１１.2.1。
在棋盘上任一点有一个中国象棋马，马走的规则为：1.马走日字 2.马只能向右走。
当N，M 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的
所有路径的数目。例如：(N=10，M=10)，(1，5)(起点)，(3，5)(终点)。
应输出2(即由(1，5)到(3，5)共有2条路径。
输入
n，m，x1，y1，x2，y2(分别表示n，m，起点坐标，终点坐标)
输出
路径数目(若不存在从起点到终点的路径，输出0。
样例输入
30 30 1 15 5 15
样例输出
8
接下来是，我的代码：
#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,1,2,2,1},dy[5]={0,-2,-1,1,2},n,m,sx,sy,ex,ey;
long long a[55][55];
int mp[55][55];
int ss(int x,int y)
{
if(a[x][y]>0)
{
return a[x][y];
}
if(a[x][y]==-1)
{
return 0;
}
long long t=0;
if(x-1>=sx&&y+2<=m)
{
t+=ss(x-1,y+2);
}
if(x-2>=sx&&y+1<=m)
{
t+=ss(x-2,y+1);
}
if(x-2>=sx&&y-1>=1)
{
t+=ss(x-2,y-1);
}
if(x-1>=sx&&y-2>=1)
{
t+=ss(x-1,y-2);
}
if(t==0)
{
a[x][y]=-1;
}
a[x][y]=t;
return a[x][y];
}
int main()
{
cin>>n>>m>>sx>>sy>>ex>>ey;
a[sx][sy]=1;
cout<<ss(ex,ey);
}
提供的超时样例：
50 50 2 5 49 6
求解，你伸出你美丽的援手之后会。。。。。。。。。😁
已AC,正确代码：
#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,-1,-2,-2,-1},dy[5]={0,-2,-1,1,2},n,m,sx,sy,ex,ey;
long long a[55][55];
long long ss(int x,int y)
{
if(a[x][y]>0)
{
return a[x][y];
}
if(a[x][y]==-1)
{
return 0;
}
long long t=0;
if(x-1>=sx&&y+2<=m)
{
t+=ss(x-1,y+2);
}
if(x-2>=sx&&y+1<=m)
{
t+=ss(x-2,y+1);
}
if(x-2>=sx&&y-1>=1)
{
t+=ss(x-2,y-1);
}
if(x-1>=sx&&y-2>=1)
{
t+=ss(x-1,y-2);
}
if(t==0)
{
a[x][y]=-1;
return 0;
}
a[x][y]=t;
return a[x][y];
}
int main()
{
cin>>n>>m>>sx>>sy>>ex>>ey;
a[sx][sy]=1;
cout<<ss(ex,ey);
}
有帮助，赞一个