记录编号	291529	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2014] 智哥的超时空传送	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.853 s
提交时间	2016-08-07 17:58:22	内存使用	0.43 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("tramcar.in","r",stdin);freopen("tramcar.out","w",stdout);chul();Cu
using namespace std;
//designed by New_Beeؼ 
const int maxn=45*45;
struct op{
	int to,next;
}r[maxn*2+45];
op t[maxn*2+45];
int p[maxn],head[maxn],nhead[maxn];
int col[maxn],dfn[maxn],low[maxn],np[maxn];
bool flag[maxn];
int tim=0,clr=0,ans=0;int n,m;
queue<int> q;
stack<int> st;
void mem(){
	while(!q.empty())q.pop();
	while(!st.empty())st.pop();
	memset(head,0,sizeof(head));
	memset(p,-1,sizeof(p));
	memset(nhead,0,sizeof(nhead));
	memset(col,0,sizeof(col));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(np,0,sizeof(np));
	memset(flag,0,sizeof(flag));
	tim=clr=ans=0;
}
void reinsert(int fr,int to){
	tim++;
	t[tim].to=to;
	t[tim].next=nhead[fr];
	nhead[fr]=tim;
}
void insert(int fr,int to){
	tim++;
	r[tim].to=to;
	r[tim].next=head[fr];
	head[fr]=tim;
}
void dfs(int x){
	flag[x]=1;
	dfn[x]=low[x]=++tim;
	st.push(x);int y;
	for(int i=head[x];i;i=r[i].next){
		y=r[i].to;
		if(!dfn[y]){
			dfs(y);
			low[x]=min(low[x],low[y]);
		}else if(flag[y])
			low[x]=min(low[x],low[y]);
	}if(dfn[x]!=low[x])return;clr++;
	do{
		y=st.top();
		st.pop();
		flag[y]=0;
		col[y]=clr;
	}while(y!=x);
}
int max(int x,int y){
	if(x>y)return x;
	return y;
}
void lessenpoint(){
	int y;
	for(int i=1;i<=clr;i++)
		for(int j=1;j<=n*m;j++)
			if(col[j]==i){
				np[i]+=p[j];
				for(int k=head[j];k;k=r[k].next){
					y=r[k].to;
					if(col[y]!=i)
						reinsert(i,col[y]);
				}
			}
}
void bfs(){
	memset(flag,0,sizeof(flag));
	memset(p,0,sizeof(p));
	while(!q.empty())q.pop();
	int x,y;			
	q.push(col[1]);
	flag[col[1]]=1;
	p[col[1]]=np[col[1]];
	ans=np[col[1]];
	while(!q.empty()){
		x=q.front();
		q.pop();
		flag[x]=0;
		for(int i=nhead[x];i;i=t[i].next){
			y=t[i].to;
			p[y]=max(p[y],p[x]+np[y]);
			ans=max(ans,p[y]);
			if(flag[y])continue;
			else q.push(y);
		}
	}
}	
void clean(){
	mem();char c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			while(c=getchar(),(c<'0'||c>'9')&&c!='*'&&c!='#');
			if(c=='#')continue;
			if(c=='*'){
				p[(i-1)*m+j]=0;
				q.push((i-1)*m+j);
			}else p[(i-1)*m+j]=c-48;
		}
	}int s,t,a;
	while(!q.empty()){
		scanf("%d%d",&s,&t);
		t++;
		a=q.front();
		q.pop();
		insert(a,s*m+t);
	}for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			if(p[i*m+j]==-1)continue;
			if(p[i*m+j+1]!=-1&&(j+1)<=m)
				insert(i*m+j,i*m+j+1);
			if(p[i*m+j+m]!=-1&&(i+1)<=n)
				insert(i*m+j,i*m+j+m);	
		}
	}
	tim=0;dfs(1);
	tim=0;lessenpoint();
	bfs();printf("%d\n",ans);
}				
void chul(){
	int t;scanf("%d",&t);
	while(t--)clean();
}
int main(){
	Begin;
}