求助!60分TLE
查看原帖
求助!60分TLE
1214833
Yuvxang楼主2024/8/27 22:21

没学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;
}
2024/8/27 22:21
加载中...