没学dp,想用类似bfs的办法做,可能是太暴力了,时间超了,尝试无果,有大佬给看看能不能剪枝做出来吗?
#include <iostream>
#include <cstdio>
using namespace std;
int Chessmap[22][22] = {0};
int Mx, My;
int Bx, By;
long long result = 0;
void is_Reachable(int x, int y){
if(x == Bx && y == By){
result += 1;
return ;
}
if(x > Bx || y > By || Chessmap[x][y] == 1)
return ;
else {
is_Reachable(x + 1, y);
is_Reachable(x, y + 1);
}
}
int main(void){
scanf("%d %d %d %d", &Bx, &By, &Mx, &My);
//标马以及马阻拦的地方
if(My - 2 >= 0){
if(Mx - 1 >= 0)
Chessmap[Mx - 1][My - 2] = 1;
if(Mx + 1 <= Bx)
Chessmap[Mx + 1][My - 2] = 1;
}
if(My - 1 >= 0){
if(Mx - 2 >= 0)
Chessmap[Mx - 2][My - 1] = 1;
if(Mx + 2 <= Bx)
Chessmap[Mx + 2][My - 1] = 1;
}
if(My + 2 <= By){
if(Mx - 1 >= 0)
Chessmap[Mx - 1][My + 2] = 1;
if(Mx + 1 <= Bx)
Chessmap[Mx + 1][My + 2] = 1;
}
if(My + 1 <= By){
if(Mx - 2 >= 0)
Chessmap[Mx - 2][My + 1] = 1;
if(Mx + 2 <= Bx)
Chessmap[Mx + 2][My + 1] = 1;
}
Chessmap[Mx][My] = 1;
is_Reachable(0, 0);
cout << result;
return 0;
}