玄关,搜索板子题56pts球条,代码带注释
查看原帖
玄关,搜索板子题56pts球条,代码带注释
670355
Nuclear_Fish_cyq楼主2024/8/24 12:28

rt,捞

#include <bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define inf INT_MAX
#define linf LLONG_MAX
#define ninf INT_MIN
#define nlinf LLONG_MIN
#define mod 998244353
#define lwbd lower_bound
#define upbd upper_bound
//#define range
using namespace std;
void read(int &x){
	cin >> x;
	return;
}
void readll(ll &x){
	cin >> x;
	return;
}void readdb(db &x){
	cin >> x;
	return;
}
ll n, sx, sy, ex, ey, f[2][60][20][20][20][20];
ll dx1[8] = {1, 2, -1, -2, 0, 0, 0, 0}, dy1[8] = {0, 0, 0, 0, 1, 2, -1, -2};//描述黑位置移动 
ll dx2[4] = {1, -1, 0, 0}, dy2[4] = {0, 0, 1, -1};//描述白位置移动 
bool check(ll x, ll y){
	return x >= 0 && x < n && y >= 0 && y < n;
}
//type=true:min,black type=false:max,white
//坐标顺序:先黑后白 
ll alpha_beta(ll now, ll nx1, ll ny1, ll nx2, ll ny2, ll alpha, ll beta, bool type){//alpha-beta剪枝 
//	cout << type << " " << now << " " << nx1 << " " << ny1 << " " << nx2 << " " << ny2 << endl; 
	if(now >= 3 * n){//下太久了 
		return inf;
	}
	if(f[type][now][nx1][ny1][nx2][ny2]){//记忆化 
		return f[type][now][nx1][ny1][nx2][ny2];
	}
	if(nx1 == nx2 && ny1 == ny2){//赢了 
		if(!type){
			return now;
		}
		else{
			return inf;
		}
	}
	if(type){//min,black
		for(int i = 0; i < 8; i++){//每种转移状态 
			ll tx = nx1 + dx1[i], ty = ny1 + dy1[i];
			if(!check(tx, ty)){
				continue;
			}
			beta = min(beta, alpha_beta(now + 1, tx, ty, nx2, ny2, alpha, beta, !type));//传递alpha和beta并更新最小上界beta,MinMax搜索 
			if(alpha >= beta){//剩下的东西不用看了(看也没用),剪枝! 
				break;
			} 
		}
		f[type][now][nx1][ny1][nx2][ny2] = beta;//记忆化 
		return beta;
	}
	else{//max,white
		for(int i = 0; i < 4; i++){//每种转移状态 
			ll tx = nx2 + dx2[i], ty = ny2 + dy2[i];
			if(!check(tx, ty)){
				continue;
			}
			alpha = max(alpha, alpha_beta(now + 1, nx1, ny1, tx, ty, alpha, beta, !type));//传递alpha和beta并更新最大下界alpha,MinMax搜索 
			if(alpha >= beta){//剩下的东西不用看了(看也没用),剪枝! 
				break;
			} 
		}
		f[type][now][nx1][ny1][nx2][ny2] = alpha;//记忆化 
		return alpha;
	}
}
//如果再忘记把题目给的1~n变为0~n-1自罚20仰卧起坐
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> sx >> sy >> ex >> ey;
	sx--;
	sy--;
	ex--;
	ey--;
	if(abs(sx - ex) + abs(sy - ey) <= 1){//特判白一步杀 
		cout << "WHITE 1" << endl;
		return 0;
	}
	cout << "BLACK " << alpha_beta(0, ex, ey, sx, sy, ninf * 10ll, inf * 10ll, false) << endl;
	return 0;
}
2024/8/24 12:28
加载中...