Description

Input

Output

Sample Input

1
2 2
11
1*
0 0

Sample Output

3

题目大意：

有一个N*M的矩阵地图，矩阵中用了多种字符代表不同的地形。假设是数字X(0~9)，则表示该区域为矿区，有X单位的矿产。

假设是"*"，则表示该区域为传送点，而且相应唯一一个目标坐标。假设是"#",，则表示该区域为山区，矿车不能进入。如今矿车的出发点在坐标(0。0)点。而且(0，0)点一定不是"#"区域。矿车仅仅能向右走、向下走或是遇到传送点的时候能够传送到指定位置。那么问题来了：矿车最多能採到多少矿。

思路：
假设把N*M个矩阵单位看做是N*M个点。编号为0~N*M。然后从一个坐标到还有一个坐标看做是两点之间的边。

到达的坐标所拥有的矿产为边的权值。那么问题就变成了：矿车从节点0出发，所能达到的最长路径。可是除了向右走和向下走的边，考虑到还有传送点和目标坐标构成的边。原图上就会多了非常多回退边。构成了非常多的有向环。

有向环的出现，使得矿车可以採到的矿产增多了一部分，仅仅要能走到有向环内，则该环内全部点的矿产都能被採到。可是问题也出来了，假设不做处理，直接搜索路径。那么矿车非常可能会走进环内不出来。

于是想到了缩点。把有向环缩为一个点。也就是强连通分量缩点。并记录强连通分量中的总矿产值。

缩点后，原图就变成了一个有向无环图(DAG)。然后又一次建立一个新图(DAG)，对新图求最长路径(用SPFA算法)，得到源点(0。0)到各点的最长路径。

从中找出最长的路径，就是所求的结果。

这题和POJ3126类似，都是缩点SPFA求最长路。POJ312解析

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#define maxn 2000+100
#define maxm 40000+100
#define INF 0x3f3f3f3f
using namespace std;
int n, m;

struct node {
    int u, v, next;
};

node edge[maxm];
int head[maxn], cnt;
int low[maxn], dfn[maxn];
int dfs_clock;
int Stack[maxn], top;
bool Instack[maxn];
int Belong[maxn];
int scc_clock;
int val[maxn];//存每一个点的矿石量
int sumval[maxn];//存每一个缩点的矿石量
vector<int>Map[maxm];
char map[100][100];

void init(){
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(val, 0, sizeof(val));
    memset(sumval, 0, sizeof(sumval));
    memset(val, 0, sizeof(val));
}

void addedge(int u, int v){
    edge[cnt] = {u, v, head[u]};
    head[u] = cnt++;
}

void getmap(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i)
        scanf("%s", map[i]);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(map[i][j] == '#') continue;

            if(i + 1 < n && map[i + 1][j] != '#')//向下走
                addedge(i * m + j, (i + 1) * m + j);
            if(j + 1 < m && map[i][j + 1] != '#')//向右走
                addedge(i * m + j, i * m + j + 1);
            val[i * m + j] = map[i][j] - '0';

            if(map[i][j] == '*'){
                val[i * m + j] = 0;
                int x, y;
                scanf("%d%d", &x, &y);
                if(map[x][y] != '#');//传送的位置可能为 #
                addedge(i * m + j, x * m + y);
            }
        }
    }
}

void Tarjan(int u){
    int v;
    low[u] = dfn[u] = ++dfs_clock;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].v;
        if(!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(Instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        scc_clock++;
        do{
            v = Stack[--top];
            sumval[scc_clock] += val[v];
            Instack[v] = false;
            Belong[v] = scc_clock;
        }
        while( v != u);
    }
}

void find(){
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(Belong, 0, sizeof(Belong));
    memset(Stack, 0, sizeof(Stack));
    memset(Instack, false, sizeof(false));
    dfs_clock = scc_clock = top = 0;
    for(int i = 0; i < n * m; ++i){
        if(!dfn[i])
            Tarjan(i);
    }
}

void suodian(){//缩点新建图
    for(int i = 1; i <= scc_clock; ++i)
        Map[i].clear();
//    for(int i = 0; i < n * m; ++i){
//        for(int j = head[i]; j != -1; j = edge[j].next){
//            int u = Belong[i];
//            int v = Belong[edge[j].v];
//            if(u != v)
//                Map[u].push_back(v);
//        }
//    }
    //上面也是一种建图方式。
    for(int i = 0; i < cnt; ++i){
        int u = Belong[edge[i].u];
        int v = Belong[edge[i].v];
        if(u != v)
            Map[u].push_back(v);
    }
}

int vis[maxn],dist[maxn];

void SPFA(){
    queue<int>q;
    memset(vis, 0, sizeof(vis));
    memset(dist, 0, sizeof(dist));
    vis[Belong[0]] = 1;
    dist[Belong[0]] = sumval[Belong[0]];
    q.push(Belong[0]);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = 0; i < Map[u].size(); ++i){
            int v = Map[u][i];
            if(dist[v] < dist[u] + sumval[v]){
                dist[v] = dist[u] + sumval[v];
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}


int main (){
    int T;
    scanf("%d", &T);
    while(T--){
        init();
        getmap();
        find();
        suodian();
        SPFA();
        sort(dist + 1, dist + scc_clock + 1);
        printf("%d\n", dist[scc_clock]);
    }
    return 0;
}