WA了,有点没看懂,求教
查看原帖
WA了,有点没看懂,求教
701531
liyan123楼主2024/5/12 23:16

rt,单看题目感觉是个“矩阵类型的dp”,马的存在相当于是在矩阵上的一些点设下了“障碍”(类似LC的机器人走障碍那道题) 之前刷题一直用LC,导致笔试碰到ACM模式的题目容易抓虾,遂决定LC和LG一起刷,但这里这道题挂掉了 coding如下

C++(幸好LG和LC一样的网页排版)

/*
dp[i][j] = dp[i-1][j] + dp[i][j-1],dp[i][j]表示到达(i,j)的路径数
*/
#include<bits/stdc++.h>
using namespace std;
//判断一个点会不会被马吃了 1会被吃,0不会
bool isHouse(int hx,int hy,int x,int y){
    return ((hx == x-1 &&hy == y-2)||(hx == x-1 &&hy == y+2)||(hx == x+1 &&hy == y-2)||(hx == x+1 &&hy == y+2)||(hx == x-2&&hy == y-1)||(hx == x+2&&hy == y-1)||(hx == x-2&&hy == y+1)||((hx == x+2&&hy == y+1)));
}
int main(){
    int B_x,B_y,M_x,M_y;
    //B点和马的坐标
    cin>>B_x>>B_y>>M_x>>M_y;
    vector<vector<int>>dp(B_x + 1,vector<int>(B_y + 1));
    dp[0][0] = 1;
    //卒的起点默认是(0,0);
    for(int y=1;y<=B_y;++y){
        if(isHouse(M_x,M_y,0,y)){
            break;
        }
        dp[0][y] += dp[0][y-1];
    }
    for(int x=1;x<=B_x;++x){
        if(isHouse(M_x,M_y,x,0)){
            break;
        }
        dp[x][0] += dp[x-1][0];
    }
    for(int x = 1;x <= B_x;++x){
        for(int y = 1;y <= B_y;++y){
            if(isHouse(M_x,M_y,x,y)) break;
            dp[x][y] = (dp[x][y-1] + dp[x-1][y]);
        }
    }
    cout<<dp[B_x][B_y];
    return 0;
}

感谢教授

2024/5/12 23:16
加载中...