mxqz dfs优化剪枝错哪里了
查看原帖
mxqz dfs优化剪枝错哪里了
326382
Thomas_Cat楼主2021/10/17 18:42

rt,已经解决T的问题了,应该是哪里错了,求帮忙看看

#include<bits/stdc++.h>
using namespace std;
int m,n,Map[105][105],sum=INT_MAX,flag[105][105],s[105][105];
int X[5]={0,0,1,0,-1};
int Y[5]={0,1,0,-1,0};
void dfs(int x,int y,int ans,int color){
    if(x==m&&y==m){
        sum=min(ans,sum);
        return;
    }
    for(int i=1;i<=4;i++){
            if((x+X[i])>0&&(x+X[i])<=m&&(y+Y[i])>0&&(y+Y[i])<=m)
            if(flag[x+X[i]][y+Y[i]]==0){
                if(Map[x][y]>0||Map[x+X[i]][y+Y[i]]>0){
                    if(Map[x+X[i]][y+Y[i]]==0){
                        if(ans+2<s[x+X[i]][y+Y[i]]){
                            s[x+X[i]][y+Y[i]]=ans+2;
                            flag[x][y]=1;
                            dfs(x+X[i],y+Y[i],ans+2,color);
                            flag[x][y]=0;
                        }
                    }
                    else if(Map[x+X[i]][y+Y[i]]==Map[x][y]){
                        if(ans<s[x+X[i]][y+Y[i]]){
                            s[x+X[i]][y+Y[i]]=ans;
                            flag[x][y]=1;
                            dfs(x+X[i],y+Y[i],ans,Map[x][y];
                            flag[x][y]=0;
                        }
                    }
                    else{
                        if(ans+1<s[x+X[i]][y+Y[i]]){
                            s[x+X[i]][y+Y[i]]=ans+1;
                            flag[x][y]=1;
                            dfs(x+X[i],y+Y[i],ans+1,Map[x][y]);
                            flag[x][y]=0;
                        }
                    }
                }
            }
    }
    return;
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=INT_MAX;
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        Map[x][y]=c+1;
    }
    flag[1][1]=1;
    dfs(1,1,0,Map[1][1]);
    cout<<sum;
    return 0;
}
2021/10/17 18:42
加载中...