题解 | 过河卒# dp+内存优化

#include <iostream>
#include <vector>
using namespace std;
struct point{
    int x;
    int y;
    point(int a=0,int b=0):x(a),y(b){}
};

bool test(vector<point> &field,int &x,int &y){
    bool result=false;
    for(const point& a:field){
        if(a.x==x&&a.y==y){
            result=true;break;}
    }
    return result;
}

int main() {
    point B, hourse;
    int i,j,cur,prev;
    long fromLeft,fromTop;
    cin>>B.x>>B.y>>hourse.x>>hourse.y;
    vector<point> horseField={{hourse.x,hourse.y}};
    for(i=0;i<8;++i){
        if(hourse.x+((i%2?1:2))*(i<4?1:-1)<=B.x && 
        hourse.y+((i%2?2:1))*(i %4 < 2? 1:-1)<=B.y
        )horseField.push_back({hourse.x+((i%2?1:2))*(i<4?1:-1),hourse.y+((i%2?2:1))*(i %4 < 2? 1:-1)});
    }
    vector<vector<long long>> dp(2,vector<long long >(B.x+1));//代表到当面格的路径数
    dp[0][0]=1;
    for(i=0;i<=B.y;++i){
        cur=i%2;
        prev=(i-1)%2;
        for(j=i?0:1;j<dp[0].size();++j){
            if(test(horseField,j,i)){
                //当前点为马或者马的攻击范围
                dp[cur][j]=0;
                
            }else{
                fromTop=i>0? dp[prev][j]:0;
                fromLeft=j>0? dp[cur][j-1]:0;
                dp[cur][j]=fromTop+fromLeft;
                
            }
        }
    };
    cout<<dp[cur][--j]<<endl;
    

}
// 64 位输出请用 printf("%lld")