P1027 （C++代码）

解题思路:





注意事项:





参考代码:

下面来解释一下这道题

刚才天笑看了一下，下面的基本都是用DFS来做的。
天笑这里借用了BFS的思想，每到一个点，就向周围的四个点拓展新节点，
然后选取最优的节点作为下一步，也就是木瓜最多的格点。
一般BFS都会用一个bool数组来记录走过的状况，
但在此题中只需要将走过的点修改使它不能成为最优点，
也就是将它赋为0。最后，一定要记得加上（1，1）和（r，c）这两个点中的木瓜！！
下面是AC代码：


#include<iostream>
using namespace std;
int a[101][101],d1[4]={0,1,-1,0},d2[4]={1,0,0,-1},r,c,ans;void search(int x,int y)
{
    ans+=a[x][y];  //带上（1，1）里的木瓜
    a[x][y]=0;    while(x!=r||y!=c)
    {        int maxn=0,maxx,maxy;        for(int i=0;i<4;i++)  //向四周拓展节点
        {            int nowx=x+d1[i];            int nowy=y+d2[i];            if(nowx>=1&&nowx<=r&&nowy>=1&&nowy<=c&&a[nowx][nowy]>maxn)  //判断是否越界与是否是最优点
            {
                maxn=a[nowx][nowy];
                maxx=nowx;
                maxy=nowy;
            }
        }
        ans+=maxn;
        a[maxx][maxy]=0;  //修改使其不能成为最优点
        x=maxx,y=maxy;
    }
}int main(){    cin>>r>>c;    for(int i=1;i<=r;i++)        for(int j=1;j<=c;j++)            cin>>a[i][j];
    search(1,1);    cout<<ans<<endl;
}
祝大家早日AC！！！