蓝桥杯算法总结

序章

现处于大学生阶段，蓝桥杯算法竞赛算是我们的入门级竞赛，所以我们必须重视起来。

在这个算法总结中，我会用通俗易懂的语言，细致地讲述相关算法，希望能通过我的笔记，为大家带来一些帮助。

内容持续更新，坚持日更！

递推和递归

递推

先简单介绍一下

递推算法：自底向上，由已知条件推导出位置结果的一种算法

核心：状态转移    边界+关系式

废话不多说，直接从题目入手理解递推思想

在这里选用信息学奥赛一本通的题：https://ybt.ssoier.cn/problem_show.php?pid=1314

题目意思理解：

从A点到B点的路径数，并且经过马能到达的点都无效，我们先做好前期的工作准备

//马走日，移动的位置（马能到达的点）
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};//标记数组
int rd[110][110]={0};//记录每个点的路径数

//将马能到达的位置全标记成1
for(int i=0;i<=7;i++){
//马的坐标(cx,cy)
int nx=cx+mx[i];
int ny=cy+my[i];
if(nx<0 || ny<0 || nx>n || ny>m)continue;
vis[nx][ny]=1;
}
//别忘了把马的初始位置也标记成1
vis[cx][cy]=1;

然后我们准备初始化边界，满足

//起点置为一
rd[0][0]=1;
//初始化左边界和上边界
for(int i=1;i<=n;i++){
rd[i][0]=rd[i-1][0];
if(vis[i][0]==1)rd[i][0]=0;
}
for(int i=1;i<=m;i++){
rd[0][i]=rd[0][i-1];
if(vis[0][i]==1)rd[0][i]=0;
}

注意题目，棋子卒能挪动的方向只有向下和向右，说明在某个点K上，到达K的路径数为K上面的点+K左面的点

所以我们可以列出关系式： rd[i][j] = rd[i-1][j]+rd[i][j-1]

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//注意：马能到达的标记处 卒无法通过
if(vis[i][j]==1)continue;
rd[i][j]=rd[i-1][j]+rd[i][j-1];
}
}

经过上述理解，我们就得到了完整代码

#include<bits/stdc++.h>
using namespace std;
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};
int rd[110][110]={0};
int main(){
int n,m,cx,cy;
cin>>n>>m>>cx>>cy;
vis[cx][cy]=1;
for(int i=0;i<=7;i++){
int nx=cx+mx[i];
int ny=cy+my[i];
if(nx<0 || ny<0 || nx>n || ny>m)continue;
vis[nx][ny]=1;
}
rd[0][0]=1;
for(int i=1;i<=n;i++){
rd[i][0]=rd[i-1][0];
if(vis[i][0]==1)rd[i][0]=0;
}
for(int i=1;i<=m;i++){
rd[0][i]=rd[0][i-1];
if(vis[0][i]==1)rd[0][i]=0;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==1)continue;
rd[i][j]=rd[i-1][j]+rd[i][j-1];
}
}
cout<<rd[n][m]<<endl;
return 0;
}

但是，我们提交后的运行结果

并没有完全AC,但其实我们的代码逻辑是没有问题的，那到底错在哪儿了？

解答一下：其实是我们的数组越界/数据范围溢出了

我们只需要修改两处

插入   #define int long long

将  int main() 修改为 signed main()

以下是真正的正确代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};
int rd[110][110]={0};
signed main(){
int n,m,cx,cy;
cin>>n>>m>>cx>>cy;
vis[cx][cy]=1;
for(int i=0;i<=7;i++){
int nx=cx+mx[i];
int ny=cy+my[i];
if(nx<0 || ny<0 || nx>n || ny>m)continue;
vis[nx][ny]=1;
}
rd[0][0]=1;
for(int i=1;i<=n;i++){
rd[i][0]=rd[i-1][0];
if(vis[i][0]==1)rd[i][0]=0;
}
for(int i=1;i<=m;i++){
rd[0][i]=rd[0][i-1];
if(vis[0][i]==1)rd[0][i]=0;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==1)continue;
rd[i][j]=rd[i-1][j]+rd[i][j-1];
}
}
cout<<rd[n][m]<<endl;
return 0;
}

小总结：

递推有两要素：边界条件和关系式

只要正确推出这两个要素，再从已知推未知，就可以轻松解决递推问题啦