Problem 2092 收集水晶

Accept: 101 Submit: 439

Time Limit: 5000 mSec Memory Limit : 32768 KB

Problem Description

shadow来到一片神奇的土地，这片土地上不时会出现一些有价值的水晶，shadow想要收集一些水晶带回去，但是这项任务太繁杂了，于是shadow让自己的影子脱离自己并成为一个助手来帮助自己收集这些水晶。

shadow把这片土地划分成n*m个小方格，某些格子会存在一些shadow和他的影子都无法穿越的障碍，比如巨石、树木、野兽等。shadow预先探测到了水晶出现的时间、位置以及它们的价值，但这些水晶的存在就如昙花一现般短暂，若在出现后1秒内没有收集到，它便将消失。

在第0秒的时候，shadow和他的影子都处在第一行第一列的格子上，shadow和他的影子可以相互独立的移动，互不干扰。每一秒shadow能移动到相邻的一格，也可以呆在原地不动，shadow的影子也是。那么，shadow和他的影子能收集到的水晶价值总和最大是多少呢？

Input

输入数据第一行包含一个整数T，表示测试数据的组数。对于每组测试数据：

第一行两个整数n、m( 2 <= n , m <= 10 )，表示土地被划分为n行，每行m列个小方格。

接下来n行，每行m个字符，’.’或者’#’， 描述土地信息，’.’表示空地，’#’表示障碍。

接下来一行包含一个整数p( p < 0 < 1000 )，表示总共会出现的水晶数量。

接下来p行，每行4个整数，t( 0 < t <= 200 )，x( 1 <= x <= n )，y( 1 <= y <= m )，v( 0 < v <= 1000 )，表示第t秒会有一个价值v的水晶出现在第x行第y列的格子里。

Output

对于每组测试数组，输出一行包含一个整数，表示shadow和他的影子能收集到的最大价值总和。

Sample Input

1

3 3

…

..#

…

3

2 3 1 3

2 2 2 2

2 1 3 1

Sample Output

5

记忆化搜索，

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

char a[15][15];

int b[201][11][11];

int dp[201][11][11][11][11];

int t;

int n,m;

int cas;

int x,y,z,p;

int maxt=0;

int dir[5][2]={{0,1},{0,-1},{1,0},{-1,0},{0,0}};

int DFS(int x1,int y1,int x2,int y2, int t)

{

    if(x1<1||x1>n||y1<1||y1>m||x2<1||x2>n||y2<1||y2>m)

                    return 0;

    if(a[x1][y1]=='#'||a[x2][y2]=='#')

                    return 0;

    if(t>maxt)

        return 0;

    if(dp[t][x1][y1][x2][y2]!=-1)

        return dp[t][x1][y1][x2][y2];

    int num=0;

        for(int i=0;i<5;i++)

        {

            for(int j=0;j<5;j++)

            {

                int xx1=x1+dir[i][0];

                int yy1=y1+dir[i][1];

                int xx2=x2+dir[j][0];

                int yy2=y2+dir[j][1];

                num=max(num,DFS(xx1,yy1,xx2,yy2,t+1));

            }

        }

        if(x1==x2&&y1==y2)

            dp[t][x1][y1][x2][y2]=num+b[t][x1][y1];

        else

            dp[t][x1][y1][x2][y2]=num+b[t][x1][y1]+b[t][x2][y2];

    return dp[t][x1][y1][x2][y2];

}

int main()

{

    scanf("%d",&cas);

    while(cas--)

    {

        memset(b,0,sizeof(b));

        cin>>n>>m;

        for(int i=1;i<=n;i++)

           scanf("%s",a[i]+1);

        scanf("%d",&p);

        for(int i=1;i<=p;i++)

        {

            scanf("%d%d%d%d",&t,&x,&y,&z);

            maxt=max(maxt,t);

            b[t][x][y]+=z;

        }

        memset(dp,-1,sizeof(dp));

        DFS(1,1,1,1,0);

        printf("%d\n",dp[0][1][1][1][1]);

    }

    return 0;

}