题解 P2958 【[USACO09OCT]木瓜的丛林Papaya Jungle】

· · 题解

Bessie不小心游荡出Farmer John的田地，而走进了相邻的农民的地里。她举起一个木瓜，木瓜对奶牛来说可是不可多得得美味。这个木瓜林像一般的威斯康星州的田地一样被分割成一个R行C列的网格(1 <= R <= 40, 1 <= C <= 40)。Bessie可以从一个格沿着一条跟X轴或Y轴平行的直线走到邻接的另一个格。Bessie发现一开始她自己在木瓜林的(1,1)，也就是第一行第一列慢悠悠地咀嚼着木瓜。 Bessie总是用她最信赖地双筒望远镜去数每一个邻接的格里挂着的木瓜的数目。然后她就游荡到那个有最多没有被吃掉的木瓜的邻接的格子（保证这样的格子只有一个）。 按照这种移动方法，最终Bessie总是会在(R,C)停止然后吃掉那里的木瓜。 给定这个木瓜林的大小及每个格的木瓜数F_ij(1 <= F_ij <= 100), 要求Bessie一共吃了多少个木瓜。

思路：只要想如何让Bessie每次走的都是周围木瓜最多的就行了

#include<bits/stdc++.h>
using namespace std;
int r,c,a[41][41],sum;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void dfs(int x,int y)
{
    sum=sum+a[x][y];
    a[x][y]=0;
    if(x==r&&y==c)
        return;
    int mx,my,ans=0;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx>=1&&tx<=r&&ty>=1&&ty<=c&&a[tx][ty]>ans)
        {
            ans=a[tx][ty];
            mx=tx,my=ty;
        }   
    }
    dfs(mx,my); 
}
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>a[i][j];
    dfs(1,1);
    cout<<sum;
}