題目大意: 給出一個n*m的格子地圖,每一格上面是0~9,“*”或“#”。如果格子上是數字代表這個格子上有目前數量的礦石。如果是“*” 代表着目前格子是一個傳送陣可以傳送到指定的地方。如果是“#”代表目前格子不可達。 現在有一個礦車在坐标(0,0),也就是左上角。他隻能向右和下行駛。當遇到傳送陣時可以被傳送到指定的位置。當他遇到數字時就可以得到那些數量的礦石,那個地方的礦石數量就變為“0”。問礦車最多可以采多少礦。
代碼實作:
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define MEM(a) (memset((a),0,sizeof(a)))
#define MEME(a) (memset((a),-1,sizeof(a)))
#define MEMX(a) (memset((a),0x3f,sizeof(a)))
using namespace std;
const int N=1605;
int dfn[N],low[N],st[N],belong[N],d[N],value[N],s_value[N],bcnt,tim,top,s_top,n,m;
bool inst[N];
char mp[45][45];
vector<int> v[N];
struct Edge{
int to;
Edge *next;
}*head[N],e[4810];
void Addedge(int from,int to){
Edge *p=&e[top++];
p->to=to;
p->next=head[from];
head[from]=p;
}
void Tarjan(int i){
dfn[i]=low[i]=++tim;
st[++s_top]=i;
inst[i]=1;
int to;
for(Edge *p=head[i];p;p=p->next){
to=p->to;
if(!dfn[to]){
Tarjan(to);
if(low[to]<low[i]) low[i]=low[to];
}else if(inst[to]&&dfn[to]<low[i]) low[i]=dfn[to];
}
if(dfn[i]==low[i]){
bcnt++;
do{
to=st[s_top--];
inst[to]=0;
belong[to]=bcnt;
s_value[bcnt]+=value[to];
}while(i!=to);
}
}
int dfs(int i){
int& ans=d[i];
if(ans>0) return ans;
ans=s_value[i];
for(int j=0;j<v[i].size();++j)
ans=Max(ans,dfs(v[i][j])+s_value[i]);
return ans;
}
int main(){
int t,x,y;
scanf("%d",&t);
while(t--){
MEM(head),MEM(dfn),MEM(low),MEM(inst),MEM(d),MEM(s_value);
bcnt=top=s_top=tim=0;
scanf("%d%d",&n,&m);
int cnt=n*m,max_value;
for(int i=0;i<cnt;++i) v[i].clear();
for(int i=0;i<n;++i) scanf("%s",mp[i]);
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(mp[i][j]=='#') continue;
if(mp[i][j]=='*') value[i*m+j]=0;
else value[i*m+j]=mp[i][j]-'0';
if(j+1<m&&mp[i][j+1]!='#') Addedge(i*m+j,i*m+j+1);
if(i+1<n&&mp[i+1][j]!='#') Addedge(i*m+j,i*m+m+j);
if(mp[i][j]=='*'){
scanf("%d%d",&x,&y);
if(mp[x][y]!='#')Addedge(i*m+j,x*m+y);
}
}
}
for(int i=0;i<cnt;++i) if(!dfn[i]) Tarjan(i);
for(int i=0;i<cnt;++i)
for(Edge *p=head[i];p;p=p->next)
if(belong[i]!=belong[p->to]) v[belong[i]].push_back(belong[p->to]);
max_value=dfs(belong[0]);
printf("%d\n",max_value);
}
}