比赛 20241127 评测结果 AWWWWWATTT
题目名称 魔法阵 最终得分 20
用户昵称 徐诗畅 运行时间 6.363 s
代码语言 C++ 内存使用 3.45 MiB
提交时间 2024-11-27 11:40:31
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m,k1,k2;
int vis[N][N],ans=0x3f3f3f3f;
struct d{
	int x,y;
}s[N*N];
int nx[4]={0,1,0,-1};
int ny[4]={1,0,-1,0};
void dfs(int x,int y,int num){
    if(x>ans) return;
	if(num==n*m){
		int res=0;
		for(int i = 1;i<=n*m/2;i++)
		res=max(res,k1*abs(s[i].x-s[i+(n*m/2)].x)+k2*abs(s[i].y-s[i+(n*m/2)].y));
		ans=min(ans,res); 
		return;
	}
	for(int i = 0;i<4;i++){
		int xx=x+nx[i],yy=y+ny[i];
		if(vis[xx][yy]||xx>n||xx<1||yy>m||yy<1) continue;
		s[num+1].x=xx; s[num+1].y=yy;
		vis[xx][yy]=1;
		dfs(xx,yy,num+1);
		vis[xx][yy]=0;
	}
}
int main(){
	freopen("mmatrix.in","r",stdin);
	freopen("mmatrix.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&k1,&k2);
	dfs(1,1,0);
	printf("%d",ans);
	return 0;
}