#include<bits/stdc++.h>
using namespace std;
int n,gs,g[51][51],mist=INT_MAX;
bool gxy[51][51],g11[51][51];
bool s;
void dfs(int x,int y,int step,int gx,int gy,int ng,bool now)
{
//    cout<<x<<" "<<y<<" "<<step<<" "<<gx<<" "<<gy<<" "<<ng<<" "<<mist<<" ## ";
//    if(s) cout<<endl;
//    s=!s;
    if(!now)
    {
        if(x==gx && y==gy)
        {
            g11[x][y]=1;
            goto t;
            g11[x][y]=0;
        }
        if(!gxy[x-1][y] && x>1)
        {
            gxy[x-1][y]=1;
            dfs(x-1,y,step+1,gx,gy,ng+g[x-1][y],0);
            gxy[x-1][y]=0;
        }
        if(!gxy[x][y+1] && y<n)
        {
            gxy[x][y+1]=1;
            dfs(x,y+1,step+1,gx,gy,ng+g[x][y+1],0);
            gxy[x][y+1]=0;
        }
        if(!gxy[x+1][y] && x<n)
        {
            gxy[x+1][y]=1;
            dfs(x+1,y,step+1,gx,gy,ng+g[x+1][y],0);
            gxy[x+1][y]=0;
        }
        if(!gxy[x][y-1] && y>1)
        {
            gxy[x][y-1]=1;
            dfs(x,y-1,step+1,gx,gy,ng+g[x][y-1],0);
            gxy[x][y-1]=0;
        }
    }
    else
    {
        t:\
        if(x==1 && y==1)
        {
            if(ng>=gs) mist=min(mist,step);
            return ;
        }
        if(!g11[x-1][y] && x>1)
        {
            g11[x-1][y]=1;
            dfs(x-1,y,step+1,0,0,(gxy[x-1][y]?ng:ng+g[x-1][y]),0);
            g11[x-1][y]=0;
        }
        if(!g11[x][y+1] && y<n)
        {
            g11[x][y+1]=1;
            dfs(x,y+1,step+1,0,0,(gxy[x][y+1]?ng:ng+g[x][y+1]),0);
            g11[x][y+1]=0;
        }
        if(!g11[x+1][y] && x<n)
        {
            g11[x+1][y]=1;
            dfs(x+1,y,step+1,0,0,(gxy[x+1][y]?ng:ng+g[x+1][y]),0);
            g11[x+1][y]=0;
        }
        if(!g11[x][y-1] && y>1)
        {
            g11[x][y-1]=1;
            dfs(x,y-1,step+1,0,0,(gxy[x][y-1]?ng:ng+g[x][y-1]),0);
            g11[x][y-1]=0;
        }
    }
}
int main()
{
    cin>>n>>gs;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    gxy[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=1 || j!=1) dfs(1,1,0,i,j,0,0);
    cout<<mist<<endl;
    return 0;
}

在我自己配数据前先写一个暴力代码 题

现在dfs中now=1时不回到1,1 求助