一、题目
过河卒题目
二、做题总结
- 本题之前在ZSC上是做过的，当初用的是DFS深度搜索，这次在洛谷上还是原来的思路，却被提示TLE！！原来在ZSC上这道题的测试数据是被简化过的，当在洛谷遇到坐标比较高的时候就超时了
- 因为没有接触过DP 虽然知道要用递推代替递归 但最后还是没想明白怎么写 查询资料之后知道了这道题可以用动态规划DP来做 很简单的状态转移方程式：
dp[i][j]=dp[i-1][j]+dp[i][j-1]
（第 dp[i][j] 个位置到达的可能性是第 dp[i-1][j] 个位置方案数 + 第 dp[i][j-1] 个位置的方案数）
三、之前解题的总结和DFS代码【会TLE】
- 题目中马以“日”字形沿各方向跳出的点才是题目中所谓马控制的九个点，而不是马坐标周围的九个点
- 题目的坐标系是以第四象限为平面，卒可向下或向右
- dfs求路径总数要设置边界（1）到达目的地结束 （2）碰到障碍物结束 （3）越界结束
#include <iostream>
using namespace std;
int m,n;
long long arr[25][25]={0};
void dfs(int x,int y,long &router)
{
if(arr[x][y]==9)
{
router++;
return;
}
if(arr[x][y]==-1) return;
if(x>m || y>n) return;
dfs(x+1,y,router);
dfs(x,y+1,router);
}
int main()
{
int a,b;
cin>>m>>n>>a>>b;
long long router=0;
//对马食的九个位置置-1
arr[a][b]=-1;
arr[a+1][b+2]=-1;
if(a-1>=0) arr[a-1][b+2]=-1;
arr[a+2][b+1]=-1;
if(a-2>=0) arr[a-2][b+1]=-1;
if(b-1>=0) arr[a+2][b-1]=-1;
if(a-2>=0 && b-1>=0) arr[a-2][b-1]=-1;
if(b-2>=0) arr[a+1][b-2]=-1;
if(a-1>=0 && b-2>=0)arr[a-1][b-2]=-1;
dfs(0,0,router);
cout<<router<<endl;
}
四、使用DP解题【AC】
- 注意：题目明确说明数据很大 所以数组声明时要用long long
#include <iostream>
using namespace std;
int m,n;
long long arr[25][25]={0};
void dp()
{
if(arr[0][0]==-1) return; //马食位置
arr[0][0]=1;
for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) //DP
if(arr[i][j]!=-1)
{
if(i && arr[i-1][j]!=-1) arr[i][j]+=arr[i-1][j];
if(j && arr[i][j-1]!=-1) arr[i][j]+=arr[i][j-1];
}
}
int main()
{
// m,n为目的坐标 a,b为马的位置
int a,b;
cin>>m>>n>>a>>b;
arr[a][b]=-1;
arr[a+1][b+2]=-1;
arr[a][b]=-1;
if(a-1>=0) arr[a-1][b+2]=-1;
arr[a+2][b+1]=-1;
if(a-2>=0) arr[a-2][b+1]=-1;
if(b-1>=0) arr[a+2][b-1]=-1;
if(a-2>=0 && b-1>=0) arr[a-2][b-1]=-1;
if(b-2>=0) arr[a+1][b-2]=-1;
if(a-1>=0 && b-2>=0)arr[a-1][b-2]=-1;
dp();
cout<<arr[m][n]<<endl;
}
