给一个n*m的图， 从0, 0这个点开始走，只能向右和向下。 图中有的格子有值， 求能获得的最大值。 其中有些格子可以传送到另外的格子， 有些格子不可以走。
将图中的每一个格子都看成一个点， 然后对它右边和下边的点连边， 如果是'#’就continue, 如果可以传送， 那么就对传送到的那个点连边， 同时也要向右边和下边连边， 因为可以选择不传送。 然后缩点求最长路就可以。
一个数组没有初始化RE了好多发.....
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {, }, {, }, {, -}, {, } };
const int maxn = ;
const int maxE = 1e5+;
int num, val[maxn], n, m, low[maxn], dfn[maxn], s[maxn], instack[maxn], st[maxn], top, cnt, cnum;
int sumval[maxn], head2[maxE], head[maxE], dis[maxn];
char g[][];
struct node
{
int to, nextt;
}e[maxE], e2[maxE];
int dfs(int u) {
if(~dis[u])
return dis[u];
int ans = sumval[u], ret = ;
for(int i = head2[u]; ~i; i = e2[i].nextt) {
int v = e2[i].to;
ret = max(ret, dfs(v));
}
return dis[u] = ret+ans;
}
void add2(int u, int v) {
e2[num].to = v;
e2[num].nextt = head2[u];
head2[u] = num++;
}
void rebuild() {
num = ;
for(int i = ; i<n*m; i++) {
int u = s[i];
for(int j = head[i]; ~j; j = e[j].nextt) {
int v = e[j].to;
if(s[v] == u)
continue;
add2(u, s[v]);
}
}
}
void tarjan(int u) {
instack[u] = ;
st[top++] = u;
dfn[u] = low[u] = ++cnt;
for(int i = head[u]; ~i; i = e[i].nextt) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[v], low[u]);
} else if(instack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
++cnum;
int x;
do {
x = st[--top];
instack[x] = ;
s[x] = cnum;
sumval[cnum] += val[x];
} while( x!=u );
}
}
int judge(int x, int y) {
if(x>=&&x<n&&y>=&&y<m&&g[x][y]!='#')
return ;
return ;
}
void add(int u, int v) {
e[num].to = v;
e[num].nextt = head[u];
head[u] = num++;
}
void build()
{
scanf("%d%d", &n, &m);
for(int i = ; i<n; i++)
scanf("%s", g[i]);
int x, y;
for(int i = ; i<n; i++) {
for(int j = ; j<m; j++) {
if(g[i][j] == '#')
continue;
if(g[i][j] == '*') {
scanf("%d%d", &x, &y);
add(i*m+j, x*m+y);
}
if(g[i][j]!='*')
val[i*m+j] = g[i][j]-'';
for(int k = ; k<; k++) {
int tmpx = i+dir[k][];
int tmpy = j+dir[k][];
if(judge(tmpx, tmpy))
add(i*m+j, tmpx*m+tmpy);
}
}
}
}
void init() {
num = top = cnum = cnt = ;
mem(dfn);
mem(sumval);
mem1(head);
mem1(head2);
mem1(dis);
mem(instack);
mem(low);
mem(val);
mem(s);
}
int main()
{
int t, ans;
cin>>t;
while(t--) {
init();
build(); //建图
tarjan(); //缩点
rebuild(); //对缩点后的图建图
ans = dfs(s[]); //记忆化搜索求最长路
cout<<ans<<endl;
}
return ;
}