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;
}
感谢教授