code vs 1216 跳马问题
题目描述 Description
题目
输入描述 Input Description
第一行两个正整数M，N(0<M,N≤300）分别表示行和列
第二行两个正整数，表示起点的行列坐标。
第三行两个正整数，表示终点的行列坐标
输出描述 Output Description
一个正整数，表示方案总数对123456求余
样例输入 Sample Input
3 3
1 1
2 3
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
1
分类标签 Tags 点此展开
思路：记忆化搜索，爆搜gg。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mod 123456 using namespace std; int f[350][350]; int n,m,sx,sy,tx,ty,ans; int dfs(int x,int y){ if(x<1||x>n||y<1||y>m) return 0; if(f[x][y]) return f[x][y]; return f[x][y]+=(dfs(x-1,y-2)+dfs(x-1,y+2)+dfs(x-2,y-1)+dfs(x-2,y+1)); } int main(){ scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty); f[sx][sy]=1; dfs(tx,ty); cout<<f[tx][ty]%mod; }