搜索路径问题 求解 代码如何修改

Question

搜索路径问题

#include<bits/stdc++.h>
using namespace std;
int move[4][2]={0,1,-1,0,0,-1,1,0};int n,i1,yi,a[20][20],sd=0,sum=0,tr=0,vis[20][20]={0};

void bfs(int x,int y)
{ int nx,ny,i,j,t=-1;
if(x==0&&y==n-1) return;
    for(i=0;i<4;i++)
    {
        nx=x+move[i][0];
        ny=y+move[i][1];
        if(nx>=0&&nx<n&&ny>=0&&ny<n&&vis[nx][ny]==0)
        {
        if(t<a[nx][ny]) 
        {t=a[nx][ny];
        i1=nx;yi=ny;}}
    }
    sum=a[i1][yi]+sum;vis[i1][yi]=1;//先算到达最多累积多少 为47 
          bfs(i1,yi);

    }
void bfs12(int x,int y)
{ int nx,ny,i,j,s;
if(x==0&&y==n-1) 
{ if(tr==sum)sd++;
return;}
    for(i=0;i<4;i++)
    {
        nx=x+move[i][0];
        ny=y+move[i][1];
        if(nx>=0&&nx<n&&ny>=0&&ny<n&&vis[nx][ny]==0)//再算多少条路的累计值为47
        { tr=tr+a[nx][ny]; vis[nx][ny]=1;bfs12(nx,ny);tr=tr-a[nx][ny];vis[nx][ny]=0;
        }



    }


}


int main(){ 
int j,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
scanf("%d",&a[i][j]);}vis[n-1][0]=1;
bfs(n-1,0);memset(vis,0,sizeof(vis));vis[n-1][0]=1;
bfs12(n-1,0);

printf("%d ",sd);//多少条累积值为最大这样的路
printf("%d",sum+a[n-1][0]);//最大累积值 
return 0;}

5
4 5 4 5 6
2 6 5 4 6
2 6 6 5 2
4 5 2 2 5
5 2 5 6 4从左下角5出发到右上角6
正确结果输出3 47 3条累积值为47的路
我的代码输出为 20 47 求问如何修改我的代码 求问大佬

Answer 1

对bfs12函数做如下局部修改即可：

        //if (nx >= 0 && nx < n&&ny >= 0 && ny < n&&vis[nx][ny] == 0)//修改前
        if (nx >= 0 && nx <= **x**&&ny >=** y** && ny < n&&vis[nx][ny] == 0) //修改后

修改前效果：

修改后效果：

总结：

1、为了他人回答方便，建议好好整理代码，确保代码的易读性。
2、搞不清楚结果的时候，可以遍历所有结果并打印出来分析，特别是可以图形化的这种问题。
3、这类问题，基本都跟限定条件错误有关，这个问题需要考虑路径的搜寻趋势，即应当符合左下向右上逐步缩小范围的要求。