记录编号	597422	评测结果	AAAAAAAAAA
题目名称	魔法阵	最终得分	100
用户昵称	黄天宇	是否通过	通过
代码语言	C++	运行时间	0.258 s
提交时间	2024-11-27 19:08:26	内存使用	3.34 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,k1,k2;
const int MAXN=105;
struct edge{
	long long x;
	long long y;
}e[MAXN];
int cx[5]={1,0,-1,0};
int cy[5]={0,1,0,-1};
int sum[MAXN];
bool mapp[MAXN][MAXN];
long long minx=1e18;
int cnt;
int s;
bool vis[MAXN][MAXN];
void dfs(int now,int xx,int yy,long long maxx){
	if(vis[xx][yy+1]&&vis[xx][yy-1]&&!vis[xx-1][yy]&&!vis[xx+1][yy]) return;
	if(vis[xx+1][yy]&&vis[xx-1][yy]&&!vis[xx][yy+1]&&!vis[xx][yy-1]) return;
	if(maxx>minx) return;
	if(now==m*n){
		minx=min(minx,maxx);
		return;
	}else
	if(now<=m*n/2){
		e[now].x=xx;
		e[now].y=yy;
	}else{
		maxx=max(maxx,k1*abs(xx-e[now-m*n/2].x)+k2*abs(yy-e[now-m*n/2].y));
	}
	for(int i=0;i<4;i++){
		int curx=xx+cx[i];
		int cury=yy+cy[i];
		if(!vis[curx][cury]){
			vis[curx][cury]=1;
			dfs(now+1,xx+cx[i],yy+cy[i],maxx);
			vis[curx][cury]=0;
		}
	}
	return;
}
int main(){
	freopen("mmatrix.in","r",stdin);
	freopen("mmatrix.out","w",stdout);
	cin>>n>>m>>k1>>k2;
	vis[1][1]=1;
	for(int i=1;i<=n;i++){
		vis[i][0]=1;
		vis[i][m+1]=1;
	}
	for(int i=1;i<=m;i++){
		vis[0][i]=1;
		vis[n+1][i]=1;
	}
	dfs(1,1,1,-1);
	cout<<minx<<endl;
	return 0;
}