P1002 题解

看到好多大佬用的搜索,本蒟蒻来个递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>//万能头 2MB一个 嘿嘿 
using namespace std;//命名空间
int main() {
int n,m,nn,mm,i,j;//定义变量
long long f[100][100];//定义二维数组[长][宽](其实[20][20]就可以了)
cin>>n>>m>>nn>>mm;//输入
nn++;//找下一个元素×1
mm++;//找下一个元素×2
n++;//找下一个元素×3
m++;//找下一个元素×4
memset(f,0,sizeof(f));//初始化数组
f[0][1]=1;//递推
for(i=1; i<=n; i++) {//行
for(j=1; j<=m; j++) {//列
if((abs(i-nn)+abs(j-mm)==3)&&(i!=nn)&&(j!=mm)||(i==nn&&j==mm));//判断距离
else f[i][j]=f[i-1][j]+f[i][j-1];//递推
}
}
cout<<f[n][m];//输出
return 0;//完美结束
}//再见rwr