題目鏈接

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
題意：給一個(gè)n×m的四連通網(wǎng)格圖，A表示起點(diǎn)，B表示終點(diǎn)，0表示障礙，其余數(shù)字表示空地，現(xiàn)在要逐個(gè)把空地轉(zhuǎn)化為障礙，當(dāng)某次轉(zhuǎn)化后起點(diǎn)和終點(diǎn)不連通時(shí)立即結(jié)束，最大化所有轉(zhuǎn)化為障礙的空地的數(shù)字之和。
題解：
很明顯可以找一條A->B的路徑，然后將不在這條路徑上的所有其他非障礙點(diǎn)加入答案，然后再選路徑上最大的點(diǎn)加入答案。
我開始是找A->B的最短路，后來發(fā)現(xiàn)不一定是這樣。
其實(shí)，最終結(jié)果就是找一個(gè)點(diǎn)，若這個(gè)點(diǎn)是最后的那個(gè)變成障礙的點(diǎn)，那么答案就是所有非障礙點(diǎn)權(quán)值之和-這個(gè)點(diǎn)到A，B的權(quán)值之和。
所以，我們可以跑兩次最短路，分別求出A和B點(diǎn)到其他點(diǎn)的最短路，然后枚舉每個(gè)點(diǎn)，當(dāng)它為最后一個(gè)點(diǎn)時(shí)的答案，取最大值就行了。
#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;}