（1/10000）洛谷 P1002 过河卒

问题描述：

• 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
  
  棋盘用坐标表示，A 点 (0, 0)、B 点(n,m)，同样马的位置坐标是需要给出的。
• 输入格式
  • 每行四个整数，分别表示B点坐标及马的坐标
• 输出格式
  • 一个整数，表示所有路径条数

问题分析

1. 对于这个问题，第一反应是通过深度优先搜索配合剪枝的形式，直接递归遍历所有可能的路径。但是实际运行后三个测试点都超时，原因大概是由于每个点都重复经过，造成时间复杂度过高。
2. 考虑题目要求，每个棋子只能向下或者向右移动，即每个点只能从其上一个或左一个点移动过来。所以到达某个点X的路径条数应该为其上一点和左一点条数之和。因此得到递推转移方程为：dp[i][j] = dp[i-1][j]+dp[i][j-1]

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int x_b,y_b;
    int x_h,y_h;
    cin>>x_b>>y_b>>x_h>>y_h;
    unsigned long long **dp = new unsigned long long*[x_b+1];  //考虑到路径条数随着B点坐标的增大，将会以指数形式递增，因此采用unsigned long long的数据类型
    
    for(int i=0;i<=x_b;i++)		//动态申请二维递推数组空间
    {
        dp[i] = new unsigned long long[y_b+1];
    }
  
    for(int i=0;i<=x_b;i++)		//初始化
    {
       for(int j=0;j<=y_b;j++)
       {
       		dp[i][j] = 0;
	   }
    }
    dp[0][0] = 1;
    
    for(int i=1;i<=x_b;i++)		//初始化第一行
    {
    	if(!((i==x_h && 0==y_h) || (i==x_h-1 && 0==y_h-2)
                || (i==x_h-2 && 0==y_h-1) || (i==x_h+1 && 0==y_h-2)
                || (i==x_h-1 && 0==y_h+2) || (i==x_h+1 && 0==y_h+2)
                || (i==x_h-2 && 0==y_h+1) || (i==x_h+2 && 0==y_h-1)
                || (i==x_h+2 && 0==y_h+1)))
                {
                    dp[i][0] = dp[i-1][0];
                }
	}
	for(int j=1;j<=y_b;j++)		//初始化第一列
    {
    	if(!((0==x_h && j==y_h) || (0==x_h-1 && j==y_h-2)
                || (0==x_h-2 && j==y_h-1) || (0==x_h+1 && j==y_h-2)
                || (0==x_h-1 && j==y_h+2) || (0==x_h+1 && j==y_h+2)
                || (0==x_h-2 && j==y_h+1) || (0==x_h+2 && j==y_h-1)
                || (0==x_h+2 && j==y_h+1)))
                {
                    dp[0][j] = dp[0][j-1];
                }
	}
    
    
    for(int i=1;i<=x_b;i++)		//递推求解
    {
        for(int j=1;j<=y_b;j++)
        {
            if(!((i==x_h && j==y_h) || (i==x_h-1 && j==y_h-2)
                || (i==x_h-2 && j==y_h-1) || (i==x_h+1 && j==y_h-2)
                || (i==x_h-1 && j==y_h+2) || (i==x_h+1 && j==y_h+2)
                || (i==x_h-2 && j==y_h+1) || (i==x_h+2 && j==y_h-1)
                || (i==x_h+2 && j==y_h+1)))
                {
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
        }
    }
    cout<<dp[x_b][y_b]<<endl;
    return 0;
}
/*int DFS(int x_a,int y_a,int x_b,int y_b,int x_h,int y_h)  //递归代码，超时
{
    if(x_a>x_b || y_a>y_b)
    {
        return 0;
    }
    else if((x_a==x_h && y_a==y_h) || (x_a==x_h-1 && y_a==y_h-2)
     || (x_a==x_h-2 && y_a==y_h-1) || (x_a==x_h+1 && y_a==y_h-2)
     || (x_a==x_h-1 && y_a==y_h+2) || (x_a==x_h+1 && y_a==y_h+2)
     || (x_a==x_h-2 && y_a==y_h+1) || (x_a==x_h+2 && y_a==y_h-1)
     || (x_a==x_h+2 && y_a==y_h+1))
    {
        return 0;
    }
    else if(x_a==x_b && y_a==y_b)
    {
        return 1;
    }
    
    int rightNum,downNum;
    rightNum = DFS(x_a+1,y_a,x_b,y_b,x_h,y_h);
    downNum = DFS(x_a,y_a+1,x_b,y_b,x_h,y_h);
    return rightNum+downNum;
}*/

代码不足

1. 每次都用一堆代码来对马及马一步可达的位置进行判断过于麻烦。应该采用二维数组首先保存所有的变化坐标（即横坐标-1对应纵坐标+2/-2），之后采用另一个数组用于保存改点是否可达（马及马一步可达的位置是卒不可达的）。
2. 对于第一行与第一列的点，需要注意不能直接全部初始为1，因为如果不可达的点位于第一行或第一列，改点向右或向下的所有点初始值应该全部为0。（最开始没有想到这一点，导致测试点三与四死活通不过）
3. 因为当B点坐标增大的时候，路径条数以指数级增加，因此需要使用unsigned long long的数据类型。
4. 需要注意当马及马一步可达点位于边界或超过边界的情况，需要额外判断。