UVALive

UVALive"/>

UVALive

题目大意：

给你一个N*M的地图，其中A是起点B是终点，0表示障碍，其他数字表示走到这个点的花费，我们现在要将没有障碍的地方逐渐放置障碍，直到A不能走到B为止，我们放置障碍得到的价值就是那个点的权值，我们希望这个权值和尽可能的大，问这个最大值。

思路：

记录sum表示所有点都能放置障碍的权值。

一开始写的是找A-->B的最短路shrot，然后记录这条路上的最大权值maxn，那么ans=sum-shrot+maxn.

然后找到一组错误数据：

1

4 4

然后更改思路：

枚举一个点作为最后一个放置障碍的点，假设这个点放置完障碍之后使得A走不到B.

那么ans=max（ans，sum-（从A到这个点的距离+从B到这个点的距离-2*这个点的权值））；

那么在一开始的时候跑两遍最短路再枚举即可。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{int x,y,len;
}now,nex;
int n,m;
int kase;
int dis[150][150];
int dis2[150][150];
char a[150][150];
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
void Bfs(int sx,int sy)
{for(int i=0;i<n;i++){for(int j=0;j<m;j++){dis[i][j]=0x3f3f3f3f;}}queue<node >s;dis[sx][sy]=0;now.x=sx;now.y=sy;now.len=0;s.push(now);while(!s.empty()){now=s.front();s.pop();for(int i=0;i<4;i++){nex.x=now.x+fx[i];nex.y=now.y+fy[i];nex.len=now.len;if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&a[nex.x][nex.y]!='0'){if(a[nex.x][nex.y]!='B')nex.len+=a[nex.x][nex.y]-'0';if(dis[nex.x][nex.y]>nex.len){dis[nex.x][nex.y]=nex.len;s.push(nex);}}}}
}
void Bfs2(int sx,int sy)
{for(int i=0;i<n;i++){for(int j=0;j<m;j++){dis2[i][j]=0x3f3f3f3f;}}queue<node >s;dis2[sx][sy]=0;now.x=sx;now.y=sy;now.len=0;s.push(now);while(!s.empty()){now=s.front();s.pop();for(int i=0;i<4;i++){nex.x=now.x+fx[i];nex.y=now.y+fy[i];nex.len=now.len;if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&a[nex.x][nex.y]!='0'){if(a[nex.x][nex.y]!='B')nex.len+=a[nex.x][nex.y]-'0';if(dis2[nex.x][nex.y]>nex.len){dis2[nex.x][nex.y]=nex.len;s.push(nex);}}}}
}
int main()
{int t;kase=0;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int sx,sy,ex,ey;for(int i=0;i<n;i++){scanf("%s",a[i]);for(int j=0;j<m;j++){if(a[i][j]=='A'){sx=i;sy=j;}if(a[i][j]=='B'){ex=i;ey=j;}}}Bfs(sx,sy);Bfs2(ex,ey);int sum=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]>='0'&&a[i][j]<='9')sum+=a[i][j]-'0';}}int output=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]!='0'&&a[i][j]!='B'&&a[i][j]!='A'){output=max(output,sum-(dis[i][j]+dis2[i][j]-2*(a[i][j]-'0')));}}}if(dis[ex][ey]==0x3f3f3f3f)printf("Case #%d: 0\n",++kase);else printf("Case #%d: %d\n",++kase,output);}
}