很多人都用spfa，但我觉得不必要，如果用spfa，代码长得多。

记忆花DFS的代码：

#include <cstring>
#include <cstdio>
#define P 1605
#define E 4805
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
struct Edge{
	int cnt,x[E],y[E],nxt[E],fst[P];
	void set(){
		cnt=0;
		memset(x,0,sizeof x);
		memset(y,0,sizeof y);
		memset(nxt,0,sizeof nxt);
		memset(fst,0,sizeof fst);
	}
	void add(int a,int b){
		if (a==b)
			return;
		y[++cnt]=b;
		x[cnt]=a;
		nxt[cnt]=fst[a];
		fst[a]=cnt;
	}
}e,e2;
int n,m,Px,Py,wei[P],we2[P];
int inst[P],st[P],vis[P],dfn[P],low[P],bh[P],ans,time,top;
int dp[P];
char str[42][42];
int Turn(int x,int y){
	return x*m+y+1;
}
void Turn_back(int x,int &a,int &b){
	x--;
	a=x/m;
	b=x%m;
}
void Tarjan_init(){
	ans=time=top=0;
	memset(inst,0,sizeof inst);
	memset(st,0,sizeof st);
	memset(vis,0,sizeof vis);
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(bh,0,sizeof bh);
}
void Tarjan(int x){
	dfn[x]=low[x]=++time;
	st[++top]=x;
	inst[x]=vis[x]=1;
	for (int i=e.fst[x];i;i=e.nxt[i])
		if (!vis[e.y[i]]){
			Tarjan(e.y[i]);
			low[x]=min(low[x],low[e.y[i]]);
		}
		else if (inst[e.y[i]])
			low[x]=min(low[x],low[e.y[i]]);
	if (dfn[x]==low[x]){
		ans++;
		bh[st[top]]=ans;
		inst[st[top]]=0;
		while (st[top--]!=x){
			bh[st[top]]=ans;
			inst[st[top]]=0;
		}
	}
}
int dfs(int x){// Remembered Dfs
	if (dp[x]>-1)
		return dp[x];
	dp[x]=0;
	for (int i=e2.fst[x];i;i=e2.nxt[i])
		dp[x]=max(dp[x],dfs(e2.y[i]));
	dp[x]+=we2[x];
	return dp[x];
}
int main(){
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);
		for (int i=0;i<n;i++)
			scanf("%s",str[i]);
		for (int i=0;i<42;i++)
			str[i][m]=str[n][i]='#';
		e.set();
		for (int i=0;i<n;i++)
			for (int j=0;j<m;j++){
				if (str[i][j]=='#'||str[i][j]=='*')
					wei[Turn(i,j)]=0;
				else
					wei[Turn(i,j)]=str[i][j]-'0';
				if (str[i][j]=='#')
					continue;
				if (str[i+1][j]!='#')
					e.add(Turn(i,j),Turn(i+1,j));
				if (str[i][j+1]!='#')
					e.add(Turn(i,j),Turn(i,j+1));
				if (str[i][j]=='*'){
					scanf("%d%d",&Px,&Py);
					if (str[Px][Py]=='#')
						continue;
					e.add(Turn(i,j),Turn(Px,Py));
				}
			}
		Tarjan_init();
		for (int i=1;i<=Turn(n-1,m-1);i++){
			Turn_back(i,Px,Py);
			if (str[Px][Py]=='#')
				continue;
			if (!vis[i])
				Tarjan(i);
		}
		memset(we2,0,sizeof we2);
		for (int i=1;i<=Turn(n-1,m-1);i++)
			we2[bh[i]]+=wei[i];
		e2.set();
		for (int i=1;i<=e.cnt;i++)
			e2.add(bh[e.x[i]],bh[e.y[i]]);
		for (int i=1;i<=ans;i++)
			dp[i]=-1;
		int res=dfs(bh[Turn(0,0)]);
		printf("%d\n",res);
	}
	return 0;
}