uvalive 7220

题目链接

Wijaya is a (self-PRoclaimed) hardcore gamer and also a talented programmer. His new game, DungeonTrap (DT), is scheduled to be published by next month. DT is a puzzle-like game and is built for bothiOS and Android platform. In each puzzle, player will be given a grid map ofN rows andM columns.Each cell in the map is either:

• starting point, represented by character ‘A’• goal point, represented by character ‘B’• obstacle, represented by character ‘0’ (zero)• empty cell, represented by character ‘1’ .. ‘9’

The game objective is to prevent an imp (the game’s character) to reach goal point from the startingpoint. From each cell, the imp can move to an adjacent cell (sharing an edge), given the destination cellis not an obstacle. To prevent the imp reaching the goal point, the player can put additional obstacleson empty cells, i.e. by transforming an empty cell into a cell with obstacle. The cost of transforming anempty cell into an obstacle is represented by the empty cell’s character; ‘1’ means the cost is 1 token,‘2’ means 2 tokens, ..., ‘9’ means 9 tokens. The player can continuously transform empty cells, giventhe puzzle is not yet solved. A puzzle is not considered as solved if and only if there exists at least oneway for the imp to reach the goal point (oh, by the way, the imp is not actually moving in the game,it’s supposed to be a puzzle).

Wijaya believes that high is the new low, and it is re ected in this game. The more tokens youspent in each puzzle, the lower your rank is (consequently, the worse player you are). For each puzzle,Wijaya wants to know the worse number of tokens that can be spent by a player.

For example, consider the following2 ×4 map.In this example, the puzzle can be solved by at most 13 tokens. These

are several possible games that might be played by the player:

The darken/underlined cells are those which are transformed.

Note that the previous example plays are not exhaustive, there are other possible plays. The playercannot transform all empty cells into obstacle with 14 tokens without winning the game rst (the bestone can do is 13).

Before the game is published, Wijaya has to do a quality check on the game. He needs to ensureall puzzles are correct and challenging. In particular, he needs your help to determine the maximumnumber of tokens can be spent by a player in each puzzle.

Input

The rst line of input containsT (T≤ 100) denoting the number of cases. Each case begins with twointegers N(2≤ N≤ 100) andM (2≤ M≤ 100) denoting the size of the map (rows and columns,respectively). In the following Nlines, each containsM characters describing the given map. Eachcharacter in the map is either: ‘A’, ‘B’, ‘0’, ‘1’, ‘2’, ..., ‘9’ which meaning has been de ned in the aboveproblem statement. It is guaranteed that ‘A’ and ‘B’ each appear exactly once and never adjacent inthe given map.

Output

For each case, output ‘Case #X:Y ’ (without quotes) in a line whereX is the case number (startsfrom 1) andY is an integer representing the maximum number of tokens can be spent by a player forthe respective case.

Note:

Explanation for 1st sample caseThis is the example from the problem statement

Explanation for 2nd sample caseThere’s no need to transform any empty cell as there’s already no way to reach ‘B’ from ‘A’.

Explanation for 3rd sample caseIn this puzzle, player needs to transforms all empty cells to win the game.

Sample Input

4240A24701B23A0490B223AB53337A496B52

Sample Output

Case #1: 13Case #2: 0Case #3: 8Case #4: 29
题意：给一个n×m的四连通网格图，A表示起点，B表示终点，0表示障碍，其余数字表示空地，现在要逐个把空地转化为障碍，当某次转化后起点和终点不连通时立即结束，最大化所有转化为障碍的空地的数字之和。
题解：
很明显可以找一条A->B的路径，然后将不在这条路径上的所有其他非障碍点加入答案，然后再选路径上最大的点加入答案。
我开始是找A->B的最短路，后来发现不一定是这样。
其实，最终结果就是找一个点，若这个点是最后的那个变成障碍的点，那么答案就是所有非障碍点权值之和-这个点到A，B的权值之和。
所以，我们可以跑两次最短路，分别求出A和B点到其他点的最短路，然后枚举每个点，当它为最后一个点时的答案，取最大值就行了。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=100+10;char g[maxn][maxn];int d[maxn][maxn],d1[maxn][maxn];int dx[]={1,0,-1,0},dy[]={0,-1,0,1};PII s,e;int n,m;bool ok(int x,int y){    return x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!='0';}int inq[maxn][maxn];PII q[maxn*maxn];void spfa(){    rep(i,1,n+1) rep(j,1,m+1) d[i][j]=inf;    d[s.first][s.second]=0;    memset(inq,0,sizeof(inq));    inq[s.first][s.second]=1;    int front=0,rear=0;    q[rear++]=s;    while(front!=rear)    {        PII u=q[front++];        if(front>=maxn*maxn) front=0;        inq[u.first][u.second]=0;        int p;        if(g[u.first][u.second]=='A') p=0;        else if(g[u.first][u.second]=='B') p=inf;  //        else p=g[u.first][u.second]-'0';        for(int i=0;i<4;i++)        {            int x=u.first+dx[i],y=u.second+dy[i];            if(ok(x,y))            {                if(d[x][y]>d[u.first][u.second]+p)                {                    d[x][y]=d[u.first][u.second]+p;                    //pre[x][y]=make_pair(u.first,u.second);                    if(inq[x][y]) continue;                    inq[x][y]=1;                    q[rear++]=make_pair(x,y);                    if(rear>=maxn*maxn) rear=0;                }            }        }    }}void spfa1(){    rep(i,1,n+1) rep(j,1,m+1) d1[i][j]=inf;    d1[e.first][e.second]=0;    memset(inq,0,sizeof(inq));    inq[e.first][e.second]=1;    int front=0,rear=0;    q[rear++]=e;    while(front!=rear)    {        PII u=q[front++];        if(front>=maxn*maxn) front=0;        inq[u.first][u.second]=0;        int p;        if(g[u.first][u.second]=='B') p=0;        else if(g[u.first][u.second]=='A') p=inf;  //        else p=g[u.first][u.second]-'0';        for(int i=0;i<4;i++)        {            int x=u.first+dx[i],y=u.second+dy[i];            if(ok(x,y))            {                if(d1[x][y]>d1[u.first][u.second]+p)                {                    d1[x][y]=d1[u.first][u.second]+p;                    //pre[x][y]=make_pair(u.first,u.second);                    if(inq[x][y]) continue;                    inq[x][y]=1;                    q[rear++]=make_pair(x,y);                    if(rear>=maxn*maxn) rear=0;                }            }        }    }}int main(){    int cas;    scanf("%d",&cas);    int kase=0;    while(cas--)    {        scanf("%d%d",&n,&m);        int sum=0;        rep(i,1,n+1)        {            scanf("%s",g[i]+1);            rep(j,1,m+1)            {                if(g[i][j]=='0') continue;                else if(g[i][j]=='A')                {                    s=make_pair(i,j);                }                else if(g[i][j]=='B')                {                    e=make_pair(i,j);                }                else                {                    sum+=g[i][j]-'0';                }            }        }        spfa();        spfa1();        if(d[e.first][e.second]==inf)        {            printf("Case #%d: 0/n",++kase);            continue;        }        int ans=0;        rep(i,1,n+1) rep(j,1,m+1)        {            if(g[i][j]!='A'&&g[i][j]!='B'&&g[i][j]!='0')            {                ans=max(ans,sum-d1[i][j]-d[i][j]);            }        }        printf("Case #%d: %d/n",++kase,ans);    }    return 0;}