记录编号	360851	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2014] 智哥的超时空传送	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-01-01 19:59:58	内存使用	0.43 MiB

#include <cmath>
#include <stack> 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define pos(x,y) ((x-1)*m+y)
#define Mem(arr,val) memset(arr,val,sizeof(arr))
const int maxn=3010;
const int maxnode=40*40+20;
struct Edge{
	int from,next,to;
}e[maxn],E[maxn];
int Start,date[maxnode],n,m,len,head[maxnode],Low[maxnode],Dfn[maxnode],Time;
int a[maxnode],num,Belong[maxnode],f[maxnode];
bool flag[maxnode];
stack<int> q;
void Insert(int x,int y){
	len++;e[len].from=x;e[len].to=y;e[len].next=head[x];head[x]=len;
}
void Addedge(int x,int y){
	len++;E[len].to=y;E[len].next=head[x];head[x]=len;
}
void Dfs(int x){
	Dfn[x]=Low[x]=++Time;flag[x]=true;q.push(x);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!Dfn[j]){
			Dfs(j);
			Low[x]=min(Low[x],Low[j]);
		}
		else if(flag[j])Low[x]=min(Low[x],Dfn[j]);
	}
	if(Low[x]==Dfn[x]){
		int k;num++;
		do{
			k=q.top();q.pop();
			flag[k]=false;Belong[k]=num;
			if(k==1)Start=num;
			if(a[k]>=0)date[num]+=a[k];
		}while(k!=x);
	}
}
int Dp(int x){
	if(f[x])return f[x];
	int Max=0;
	for(int i=head[x];i;i=E[i].next){
		int j=E[i].to;
		Max=max(Max,Dp(j));
	}
	return (f[x]=Max+date[x]);
}
void Init();
int main(){
	freopen("tramcar.in","r",stdin);freopen("tramcar.out","w",stdout);
	int T=0;scanf("%d",&T);
	while(T--)Init();
    getchar();getchar();
    return 0;
}
void Init(){
	Mem(flag,0);Mem(a,0);Mem(date,0);Mem(Belong,0);num=0;Time=0;len=0;
	Mem(head,0);Mem(f,0);Mem(Dfn,0);Mem(Low,0);while(!q.empty())q.pop();
	Mem(e,0);Mem(E,0);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char ch;scanf(" %c",&ch);
			if(ch=='#')a[pos(i,j)]=-2;
			else if(ch=='*')a[pos(i,j)]=-1;
			else a[pos(i,j)]=ch-48;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int k=pos(i,j);
			if(a[k]==-1){
				int x,y;scanf("%d%d",&x,&y);
				x++;y++;
				Insert(k,pos(x,y));
			} 
			if(a[k]==-2)continue;
			if(a[k+1]!=-2 && j<m)Insert(k,k+1);
			if(a[k+m]!=-2 && i<n)Insert(k,k+m);
		}
	}
	for(int i=1;i<=n*m;i++)if(!Dfn[i])Dfs(i);
	int z=len;memset(head,0,sizeof(head));len=0;
	for(int i=1;i<=z;i++){
		int fr=e[i].from,to=e[i].to;
		if(Belong[fr]!=Belong[to])Addedge(Belong[fr],Belong[to]); 
	}
	printf("%d\n",Dp(Start));
}