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

#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int n,m,k1,k2,k;
int vis[MAXN][MAXN];
int a[MAXN][2];
int maxx,ans=1e9;
int cx[5]={0,1,-1,0,0};
int cy[5]={0,0,0,1,-1};
void dfs(int x,int y,int now,int maxx){
    if(vis[x+1][y]&&vis[x-1][y]&&!vis[x][y+1]&&!vis[x][y-1])return ;
    if(!vis[x+1][y]&&!vis[x-1][y]&&vis[x][y+1]&&vis[x][y-1])return ;
    if(maxx>ans)return ;
    if(now<=k){
        a[now][0]=x;
        a[now][1]=y;
    }else maxx=max(maxx,abs(x-a[now-k][0])*k1+abs(y-a[now-k][1])*k2);
    if(now==n*m){
        ans=min(ans,maxx);
        return ;
    }
    for(int i=1;i<=4;i++){
        int curx=x+cx[i];
        int cury=y+cy[i];
        if(!vis[curx][cury]){
            vis[curx][cury]=1;
            dfs(curx,cury,now+1,maxx);
            vis[curx][cury]=0;
        }
    }
}
int main(){
    freopen("mmatrix.in","r",stdin);
    freopen("mmatrix.out","w",stdout);
    vis[1][1]=1;
    cin>>n>>m>>k1>>k2;
    k=n*m/2;
    for(int i=1;i<=n;i++){
        vis[i][0]=vis[i][m+1]=1;
    }
    for(int i=1;i<=m;i++){
        vis[0][i]=vis[n+1][i]=1;
    }
    dfs(1,1,1,0);
    cout<<ans<<endl;
    return 0;
}