欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P1585 魔法阵

程序员文章站 2022-04-13 13:38:53
"题目传送门" 这题就是一个有技巧的DFS+一大堆乱七八糟的剪枝 进行DFS时注意一下以下点 根据题意,我们可以把DFS分成两块,即 与``n m/2 n m``,第一块边找边记录,第二块就开始计算 其实左上角与右上角开始没有任何区别 剪枝 1. 可行性剪枝:判断上下与左右走过没有 2. 最优性剪枝 ......

题目传送门

这题就是一个有技巧的dfs+一大堆乱七八糟的剪枝

进行dfs时注意一下以下点

  • 根据题意,我们可以把dfs分成两块,即1--n*m/2n*m/2--n*m,第一块边找边记录,第二块就开始计算

  • 其实左上角与右上角开始没有任何区别


剪枝

  1. 可行性剪枝:判断上下与左右走过没有

洛谷P1585 魔法阵

(画风丑,勿喷)如图所示,当上下两格都走过或左右两个都走过时,
无论怎么走也是遍历完整张图的(自己去画画看就知道了)
  1. 最优性剪枝:判断当前最大值是否大于答案

这样下来就行了

看代码:

#include<bits/stdc++.h>
using namespace std;
int t,n,m,k1,k2,ans=0x3f3f3f3f;
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};//四个方向
int num[60][2];//用于第一次记录,下面会提
bool vis[60][60];//标记走过没
inline void dfs(int x,int y,int sum,int maxn)//x表示当前x坐标,y表示当前y坐标,sum表示当前步数,maxn表示当前最大值
{
    //cout<<x<<" "<<y<<" "<<sum<<" "<<maxn<<endl;
    if(vis[x-1][y]&&vis[x+1][y]&&!vis[x][y+1]&&!vis[x][y-1])return;//可行性剪枝1
    if(vis[x][y-1]&&vis[x][y+1]&&!vis[x+1][y]&&!vis[x-1][y])return;//可行性剪枝2
    if(sum<=t)num[sum][0]=x,num[sum][1]=y;//记录,这里t指一半
    else
    {
        maxn=max(maxn,k1*abs(num[sum-t][0]-x)+k2*abs(num[sum-t][1]-y));//进行计算并更新
        //return;
    }
    if(sum>=n*m)
    {
        ans=min(ans,maxn);//如果遍历完,那么更新答案
        return;
    }
    if(maxn>=ans)return;//最优性剪枝
    /*for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=m+1;j++)cout<<vis[i][j];
        cout<<endl;
    }*/
    
    for(int i=1;i<=4;i++)//四个方向枚举
    {
        int a=x+dx[i],b=y+dy[i];
        if(!vis[a][b])
        {   
            vis[a][b]=1;
            //cout<<sum<<endl;
            dfs(a,b,sum+1,maxn);
            //cout<<sum<<endl;
            vis[a][b]=0;//回溯
        }
    }
    
}
int main()
{
    cin>>n>>m>>k1>>k2;
    t=n*m/2;
    for(int i=0;i<=m+1;i++)
    {
        vis[0][i]=1;
        vis[n+1][i]=1;
    }//在外围加个边框1
    for(int i=0;i<=n+1;i++)
    {
        vis[i][0]=1;
        vis[i][m+1]=1;
    }//在外围加个边框2
    vis[1][1]=1;//初始标记
    /*num[1][0]=1;
    num[1][0]=1;
    /*for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=m+1;j++)cout<<vis[i][j];
        cout<<endl;
    }*/
    dfs(1,1,1,0);
    cout<<ans<<endl;
    return 0;
}