zju2278 -- fight for food.cpp

Zhejiang University Online Judge 第2277题至第2283题的代码和解题报告

// PROB         Zju Online Judge 2278 
// Algorithm    DP
// Complexity   -
// Author       LoveShsean
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define maxr 12
#define maxn 30010
#define check(x,y) (x >= 0 && y >= 0 && x < r && y < c && map [x] [y] == '.')

const int dx [4] = {-1, 0, 1, 0};
const int dy [4] = {0, 1, 0, -1};

using namespace std;

int r, c, N, ans;
char map [maxr] [maxr];
int x, y;
int dist [maxr] [maxr] [maxr] [maxr], far [maxr] [maxr];
int qx [maxr * maxr], qy [maxr * maxr];
int f [maxn], opt [maxn];

struct Trat
{
    int X, Y, T;
} rat [maxn];

bool init ();
void solve ();
void out ();
void BFS (int, int);
bool cmp (const Trat &, const Trat &);

int main ()
{
    while (init ())
    {
        solve ();
        out ();
    }
    return 0;
}

bool init ()
{
    int i, j;
    if (scanf ("%d%d", &r, &c) != 2) return false;
    gets (map [0]);
    for (i = 0; i < r; i ++) 
    {
        gets (map [i]);
        for (j = 0; j < c; j ++)
            if (map [i] [j] == 'L')
            {
                map [i] [j] = '.';
                x = i, y = j;
            }
    }

    memset (dist, 0xff, sizeof (dist));
    BFS (x, y);
    for (i = 0; i < r; i ++)
        for (j = 0; j < c; j ++)
            if (dist [x] [y] [i] [j] > 0) BFS (i, j);

    for (scanf ("%d", &j), i = N = 0; i < j; i ++)
    {
        ++ N;
        scanf ("%d%d%d", &rat [N].X, &rat [N].Y, &rat [N].T);
        rat [N].X --, rat [N].Y --;
        if (dist [x] [y] [rat [N].X] [rat [N].Y] < 0) N --;
    }
    
    return true;
}

void solve ()
{
    int i, j;
    sort (rat + 1, rat + N + 1, cmp);

    for (opt [0] = 0, i = 1; i <= N; i ++)
    {
        f [i] = 0;
        if (rat [i].T >= dist [x] [y] [rat [i].X] [rat [i].Y])
        {
            for (j = i - 1; j > 0 && rat [i].T - rat [j].T < far [rat [i].X] [rat [i].Y]; j --)
                if (dist [rat [j].X] [rat [j].Y] [rat [i].X] [rat [i].Y] <= rat [i].T - rat [j].T)
                    f [i] >?= f [j];
            if (j > 0) f [i] >?= opt [j];
            f [i] ++;
        }
        opt [i] = f [i] > opt [i - 1] ? f [i] : opt [i - 1];
    }

    ans = opt [N];
}

void out ()
{
    printf ("%d\n", ans);
}

void BFS (int sx, int sy)
{
    int op, ed, tx, ty, k;
    for (op = -1, ed = 0, qx [0] = sx, qy [0] = sy, dist [sx] [sy] [sx] [sy] = 0; op ++ < ed; )
        for (k = 0; k < 4; k ++)
        {
            tx = qx [op] + dx [k]; ty = qy [op] + dy [k];
            if (check (tx, ty) && dist [sx] [sy] [tx] [ty] < 0)
            {
                qx [++ ed] = tx; qy [ed] = ty;
                dist [sx] [sy] [tx] [ty] = dist [sx] [sy] [qx [op]] [qy [op]] + 1;
            }
        }
    far [sx] [sy] = dist [sx] [sy] [qx [ed]] [qy [ed]];
}

bool cmp (const Trat &a, const Trat &b)
{
    return a.T < b.T;
}