挖金子(1095)
题目描述
你在一个N*M的区域中，一开始在(1,1)的位置，每个位置有可能有金子，也有可能不能到达，也有可能有传送门。你只能往右或者下走，不能走出这个区域。当你位于传送门时，传送门你可以选择使用或者不使用，使用的次数无限，若使用则传送到传送门指定的位置。每个位置的金子你可以拿走它，问最后你最多能够拿走多少金子。
输入
首先测试数据组数T。
对于每组测试数据，先输入两个整数N,M（2<=N,M<=40）。
接下来是一个N*M的矩阵，表示每个位置的内容X，若0<=X<=9，表示该位置的金子个数为X，若X为'*'，表示该位置有一个传送门，若X为'#'，表示该位置不可到达。
假设传送门的个数为K个，接下来K行，每行两个整数x,y(0<=x<n,0<=y<m)，依次表示每个传送门传送的位置，顺序是从第一行开始从上到下扫描，每一行从左往右扫描。
输出
对于每组数据，输出能够得到的最多的金子的个数。
样例输入
1
2 2
11
1*
0 0
样例输出
3
好累、- -
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1610 int n,m;
int top;
int bcnt;
int Index;
int dfn[N];
int low[N];
int stack[N];
int belong[N];
bool instack[N];
vector<int> v1[N],v2[N]; int tn,k;
int dp[N];
int gold[N];
int mpt[][];
int num[][];
pair<int,int> p[N];
int dir[][]={,,,}; void init1()
{
k=tn=;
for(int i=;i<n*m;i++){
v1[i].clear();
v2[i].clear();
}
}
void init2()
{
top=-;
bcnt=Index=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(instack,,sizeof(instack));
}
void tarjan(int u,int pre)
{
int son=,v;
dfn[u]=low[u]=++Index;
instack[u]=;
stack[++top]=u;
for(int i=;i<v1[u].size();i++){
v=v1[u][i];
if(!dfn[v]){
son++;
tarjan(v,u);
if(low[u]>low[v]) low[u]=low[v];
}
else if(instack[v] && low[u]>dfn[v])
low[u]=dfn[v];
}
if(dfn[u]==low[u]){
bcnt++;
do{
v=stack[top--];
instack[v]=;
belong[v]=bcnt;
}while(v!=u);
}
}
int dfs(int u)
{
if(dp[u]!=-) return dp[u];
dp[u]=gold[u];
for(int i=;i<v2[u].size();i++){
int v=v2[u][i];
dp[u]=max(dp[u],gold[u]+dfs(v));
}
return dp[u];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init1();
for(int i=;i<n;i++){ //编号
for(int j=;j<m;j++){
scanf(" %c",&mpt[i][j]);
if(mpt[i][j]!='#') num[i][j]=tn++;
if(mpt[i][j]=='*') p[k++]=make_pair(i,j);
}
}
for(int i=;i<k;i++){ //建图1
int tx,ty;
scanf("%d%d",&tx,&ty);
v1[num[p[i].first][p[i].second]].push_back(num[tx][ty]);
}
for(int i=;i<n;i++){ //建图2
for(int j=;j<m;j++){
if(mpt[i][j]=='#') continue;
for(int k=;k<;k++){
int tx=i+dir[k][];
int ty=j+dir[k][];
if(tx>= && tx<n && ty>= && ty<m && mpt[tx][ty]!='#')
v1[num[i][j]].push_back(num[tx][ty]);
}
}
}
init2();
for(int i=;i<tn;i++){ //Tarjan
if(!dfn[i]) tarjan(i,i);
}
memset(gold,,sizeof(gold));
for(int i=;i<n;i++){ //计算金币
for(int j=;j<m;j++){
if(mpt[i][j]>='' && mpt[i][j]<='') gold[belong[num[i][j]]]+=mpt[i][j]-'';
}
}
for(int i=;i<tn;i++){ //缩点建图
for(int j=;j<v1[i].size();j++){
if(belong[i]!=belong[v1[i][j]])
v2[belong[i]].push_back(belong[v1[i][j]]);
}
}
memset(dp,-,sizeof(dp));
int ans=dfs(belong[]); //记忆化搜索
printf("%d\n",ans);
}
return ;
}