【題意】：給出一個(gè)n*m的矩陣，每個(gè)格子可能放有0~9，#，*。0~9代表貨物的數(shù)量，#代表阻礙，不能夠走，*代表傳送點(diǎn)，可以瞬間傳送到特定的位置，對(duì)于傳送點(diǎn)的傳送功能可以無限使用，也可以不用。初始時(shí)你開著一輛小卡車在最左上角，每一次你都可以向右走一格或者向下走一格，如果該格子上放有貨物的話你可以把他拿走，但只能拿一次。問最后你能夠拿到最多的貨物是多少？
【題解】：這是一道方格取數(shù)的變形題目，加入了阻礙與傳送點(diǎn)。如果按平時(shí)方格取數(shù)那樣做的話，由于傳送點(diǎn)的存在，圖中可能有環(huán)從而導(dǎo)死循環(huán)。于是我們想到了縮點(diǎn)，縮點(diǎn)后的新圖顯然是一個(gè)有向無環(huán)圖，對(duì)于同一連通分量上的貨物我們都可以拿走，這里留給大家自己思考為什么了，之后該怎么做就怎么做了。實(shí)際操作時(shí)，我們可以先按平時(shí)的方格取數(shù)構(gòu)圖，對(duì)于傳送點(diǎn)i，假設(shè)si是傳送點(diǎn)的本身位置，ti是傳送點(diǎn)的目標(biāo)位置，連邊si->ti，然后進(jìn)行縮點(diǎn)構(gòu)新圖，縮點(diǎn)之后的做法有很多，DP、搜索、求最長路都可以，我這里是求最長路。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "vector"
5 #include "queue"
6 using namespace std;
7 #define maxn 1605
8 const int inf = 1 << 30;
9 struct Edge {
10 int v, w;
11 };
12 int n, m;
13 char maz[50][50];
14 int dfn[maxn], low[maxn], Dindex, scc, belong[maxn], dist[maxn], score[maxn], w[maxn];;
15 int magic[maxn], cnt;
16 int s[maxn], top;
17 bool instack[maxn], visit[maxn];
18 vector<int> vec[maxn];
19 vector<Edge> dag[maxn];
20
21 void dfs(int u) {
22 int v;
23 dfn[u] = low[u] = ++Dindex;
24 s[++top] = u;
25 instack[u] = true;
26 int size = vec[u].size();
27 for(int i = 0; i < size; i++) {
28 v = vec[u][i];
29 if(!dfn[v]) {
30 dfs(v);
31 low[u] = min(low[v], low[u]);
32 } else if(instack[v]) low[u] = min(low[u], dfn[v]);
33 }
34 if(dfn[u] == low[u]) {
35 w[++scc] = 0;
36 do {
37 v = s[top--];
38 instack[v] = false;
39 belong[v] = scc;
40 w[scc] += score[v];
41 }while(v != u);
42 }
43 }
44
45 void tarjan() {
46 top = scc = Dindex = 0;
47 memset(instack, false, sizeof(instack));
48 memset(dfn, 0, sizeof(dfn));
49 for(int i = 0; i < n * m; i++)
50 if(!dfn[i]) dfs(i);
51 for(int u = 0; u < n * m; u++) {
52 int size = vec[u].size();
53 for(int i = 0; i < size; i++) {
54 int v = vec[u][i];
55 if(belong[u] != belong[v]) {
56 Edge e = {belong[v], w[belong[v]]};
57 dag[belong[u]].push_back(e);
58 }
59 }
60 }
61 Edge e = {belong[0], w[belong[0]]};
62 dag[0].push_back(e);
63 }
64
65 int spfa(int s) {
66 fill(&dist[0], &dist[maxn], -inf);
67 memset(visit, false, sizeof(visit));
68 dist[s] = 0, visit[s] = true;
69 queue<int> que;
70 que.push(s);
71 while(!que.empty()) {
72 int u = que.front();
73 que.pop();
74 visit[u] = false;
75 int size = dag[u].size();
76 for(int i = 0; i < size; i++) {
77 int v = dag[u][i].v, w = dag[u][i].w;
78 if(dist[v] < dist[u] + w) {
79 dist[v] = dist[u] + w;
80 if(!visit[v]) {
81 que.push(v);
82 visit[v] = false;
83 }
84 }
85 }
86 }
87 int ans = 0;
88 for(int i = 0; i <= scc; i++)
89 ans = max(ans, dist[i]);
90 return ans;
91 }
92
93 int main() {
94 int T;
95 scanf("%d", &T);
96 while(T--) {
97 scanf("%d%d", &n, &m);
98 getchar();
99 cnt = 0;
100 for(int i = 0; i < maxn; i++) vec[i].clear(), dag[i].clear();
101 for(int i = 0; i < n; i++) scanf("%s", maz[i]);
102 for(int i = 0; i < n; i++) {
103 for(int j = 0; j < m; j++) {
104 int u = i * m + j;
105 if(maz[i][j] == '#') score[u] = -1;
106 else {
107 if(maz[i][j] == '*') {
108 magic[cnt++] = u;
109 score[u] = 0;
110 }
111 else score[u] = maz[i][j] - '0';
112 if(j + 1 < m && maz[i][j+1] != '#') vec[u].push_back(u + 1);
113 if(i + 1 < n && maz[i+1][j] != '#') vec[u].push_back(u + m);
114 }
115 }
116 }
117 for(int i = 0; i < cnt; i++) {
118 int ii, jj, v;
119 scanf("%d%d", &ii, &jj);
120 v = ii * m + jj;
121 if(score[v] == -1) continue;
122 vec[magic[i]].push_back(v);
123 }
124 tarjan(); //縮點(diǎn)構(gòu)新圖 - dag
125 cout << spfa(0) << endl;
126 }
127 return 0;
128 }