tyvj 1027 木瓜地简单模拟

P1027 木瓜地

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

USACO OCT09 4TH

描述

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一共吃了
多少个木瓜。

输入格式

* 第一行: 两个空格隔开的整数R和C.

* 第2到R+1行: 第i+1行有C个空格隔开的整数，表示第i行的每个格的水果数。也就是F_i1,
F_i2, ..., F_iC.

输出格式

* 第一行: 一个单独的整数，表示到Bessie吃完右下角(R,C)的木瓜回到牛棚的时候為止，
一共在木瓜林吃掉了多少个木瓜。

测试样例1

输入

3 4
3 3 4 5
4 5 3 2
1 7 4 2

输出

39

简单模拟；不说了；

#include<bits/stdc++.h>
using namespace std;
#define ll __int64
#define mod 100000007
#define esp 0.00000000001
const int N=1e3+10,M=1e6+10,inf=1e9;
int a[N][N];
int flag[N][N];
int x,y,ans;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int check(int u,int v)
{
    if(u<1||u>x||v<1||v>y)
    return 0;
    return 1;
}
void dfs(int x,int y,int c,int k)
{
    ans+=a[x][y];
    if(c==x&&y==k)
    return;
    flag[x][y]=1;
    int maxx=0;
    int g=0,h=0;
    for(int i=0;i<4;i++)
    {
        int xxx=x+xx[i];
        int yyy=y+yy[i];
        if(check(xxx,yyy)&&flag[xxx][yyy]==0)
        {
            if(a[xxx][yyy]>=maxx)
            {
                maxx=a[xxx][yyy];
                g=xxx;
                h=yyy;
            }
        }
    }
    dfs(g,h,c,k);
}
int main()
{
    int z,i,t;
    scanf("%d%d",&x,&y);
    for(i=1;i<=x;i++)
    for(t=1;t<=y;t++)
    scanf("%d",&a[i][t]);
    dfs(1,1,x,y);
    printf("%d
",ans);
    return 0;
}