[swustoj 1095] 挖金子

挖金子(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 1610int 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[45][45];int num[45][45];pair<int,int> p[N];int dir[2][2]={1,0,0,1};void init1(){k=tn=0;for(int i=0;i<n*m;i++){v1[i].clear();v2[i].clear();}}void init2(){top=-1;bcnt=Index=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(instack,0,sizeof(instack));}void tarjan(int u,int pre){int son=0,v;dfn[u]=low[u]=++Index;instack[u]=1;stack[++top]=u;for(int i=0;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]=0;belong[v]=bcnt;}while(v!=u);}}int dfs(int u){if(dp[u]!=-1) return dp[u];dp[u]=gold[u];for(int i=0;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=0;i<n;i++){ //编号for(int j=0;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=0;i<k;i++){ //建图1int tx,ty;scanf("%d%d",&tx,&ty);v1[num[p[i].first][p[i].second]].push_back(num[tx][ty]);}for(int i=0;i<n;i++){ //建图2for(int j=0;j<m;j++){if(mpt[i][j]=='#') continue;for(int k=0;k<2;k++){int tx=i+dir[k][0];int ty=j+dir[k][1];if(tx>=0 && tx<n && ty>=0 && ty<m && mpt[tx][ty]!='#')v1[num[i][j]].push_back(num[tx][ty]);}}}init2();for(int i=0;i<tn;i++){ //Tarjanif(!dfn[i]) tarjan(i,i);}memset(gold,0,sizeof(gold));for(int i=0;i<n;i++){ //计算金币for(int j=0;j<m;j++){if(mpt[i][j]>='0' && mpt[i][j]<='9') gold[belong[num[i][j]]]+=mpt[i][j]-'0';}}for(int i=0;i<tn;i++){ //缩点建图for(int j=0;j<v1[i].size();j++){if(belong[i]!=belong[v1[i][j]])v2[belong[i]].push_back(belong[v1[i][j]]);}}memset(dp,-1,sizeof(dp));int ans=dfs(belong[0]); //记忆化搜索printf("%d\n",ans);}return 0;}