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
bfs，注意判斷越界，資料中有兩個水晶在同一時間位置的。
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2e2+10;
int T,n,m,p,t,x,y,ans,z;
char s[maxn];
int v[maxn][12][12],f[maxn][12][12][12][12];
int map[maxn][maxn];
struct point
{
int x1,x2,y1,y2,t;
point(int x1,int y1,int x2,int y2,int t):x1(x1),y1(y1),x2(x2),y2(y2),t(t){}
};
int a[5]={0,0,1,-1,0};
int b[5]={-1,1,0,0,0};
void bfs()
{
queue<point> p;
p.push(point(1,1,1,1,0));
f[0][1][1][1][1]=0;
while (!p.empty())
{
point q=p.front(); p.pop();
if (q.t>200) break;
for (int i=0;i<5;i++)
{
for (int j=0;j<5;j++)
{
int t=q.t+1;
int x1=q.x1+a[i],y1=q.y1+b[i];
int x2=q.x2+a[j],y2=q.y2+b[j];
if (map[x1][y1]+map[x2][y2]<2) continue;
int k=f[q.t][q.x1][q.y1][q.x2][q.y2];
k+=v[t][x1][y1]+v[t][x2][y2];
if (x1==x2&&y1==y2) k-=v[t][x1][y1];
if (f[t][x1][y1][x2][y2]<k)
{
if (f[t][x1][y1][x2][y2]==-1)p.push(point(x1,y1,x2,y2,t));
f[t][x1][y1][x2][y2]=k;
ans=max(ans,k);
}
}
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
for (int i=1;i<=n;i++)
{
scanf("%s",s);
for (int j=1;j<=m;j++) if (s[j-1]=='.') map[i][j]=1;
}
memset(v,0,sizeof(v));
memset(f,-1,sizeof(f));
scanf("%d",&p);
while (p--)
{
scanf("%d%d%d%d",&t,&x,&y,&z);
v[t][x][y]+=z;
}
ans=0; bfs();
printf("%d\n",ans);
}
return 0;
}