前言

广搜真的会超时。。。

大意

给定起点和终点，规定只能向右走，问走到终点的方案数 注意：不一定要是最优路径！

思路

因为不需要是最优路径，所以广搜的优势没了，变成了慢得要死的深搜。。。 所以要用记搜或者 dp d p

bfs代码（50分）

时间复杂度:

O(4ans(x2−x1)×(y2−y1)) O ( 4 a n s ( x 2 − x 1 ) × ( y 2 − y 1 ) )

就是这么慢

#include<cstdio> #include<queue> using namespace std;int ans,n,m; struct node{int x,y;}a,b; queue<node>q; const short dx[4]={-2,-1,1,2}; const short dy[4]={1,2,2,1}; int abs(int x){return x<0?-x:x;} bool check(node x) { if(x.y>b.y) return false;//优化1 if(x.y==b.y&&abs(x.x-b.x)&1==0) return false;//优化2 if(x.x<1||x.y<1||x.x>n||x.y>m) return false; return true; } void bfs(node s,node t) { q.push(s); while(q.size()) { node x=q.front();q.pop(); for(int i=0;i<4;i++) { node y=(node){x.x+dx[i],x.y+dy[i]}; if(check(y)) { q.push(y); if(y.x==t.x&&y.y==t.y) {ans++;break;}//累计答案 } } } } int main() { scanf("%d%d%d%d%d%d",&n,&m,&a.y,&a.x,&b.y,&b.x); bfs(a,b); printf("%d",ans);//输出 }

dp代码

#include<cstdio> using namespace std;int x1,x2,y1,y2,n,m; long long f[53][53]; const short dx[4]={1,1,2,2}; const short dy[4]={2,-2,-1,1}; int main() { scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2); f[x1][y1]=1; for(int i=1;i<=n;i++)//此处i=1可以改成i=x1，以便剪枝 for(int j=1;j<=m;j++) if(f[i][j])//剪枝 for(int k=0;k<4;k++) f[i+dx[k]][j+dy[k]]+=f[i][j]; printf("%lld",f[x2][y2]); }