记录编号	597400	评测结果	AAAAAAAAAA
题目名称	魔法阵	最终得分	100
用户昵称	孤独的氢离子	是否通过	通过
代码语言	C++	运行时间	0.194 s
提交时间	2024-11-27 16:16:58	内存使用	3.32 MiB

#include <bits/stdc++.h>
using namespace std;
int n,m,k1,k2;
int o[2600][3];
int vis[55][55];
int ans=1e9;
void dfs(int x,int y,int p,int mx)
{
	if(mx>ans) return;
	if(p<=n*m/2)
	{                  
		o[p][0]=x; 
		o[p][1]=y;
	}
	if(p>n*m/2)
	{
		int s1=abs(k1*(o[p-n*m/2][0]-x))+abs(k2*(o[p-n*m/2][1]-y));
		if(s1>mx) mx=s1;
	}
	if(p==n*m)
	{
		if(ans>mx) ans=mx;
		return ;
	}
	if(vis[x+1][y]==0&&vis[x-1][y]==0&&vis[x][y+1]==1&&vis[x][y-1]==1) return;
	if(vis[x+1][y]==1&&vis[x-1][y]==1&&vis[x][y+1]==0&&vis[x][y-1]==0) return;
	p++;
	if(vis[x-1][y]==0)
	{
		vis[x-1][y]=1;
		dfs(x-1,y,p,mx);
		vis[x-1][y]=0;
	}
	if(vis[x][y-1]==0)
	{
		vis[x][y-1]=1;
		dfs(x,y-1,p,mx);
		vis[x][y-1]=0;
	}
	if(vis[x+1][y]==0)
	{
		vis[x+1][y]=1;
		dfs(x+1,y,p,mx);
		vis[x+1][y]=0;
	}
	if(vis[x][y+1]==0)
	{
		vis[x][y+1]=1;
		dfs(x,y+1,p,mx);
		vis[x][y+1]=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=0;i<=n+1;i++)
	{
		vis[i][0]=1;
		vis[i][m+1]=1;
	}
	for(int i=0;i<=m+1;i++)
	{
		vis[0][i]=1;
		vis[n+1][i]=1;
	}
	dfs(1,1,1,0);
	cout<<ans;
	return 0; 
}