1.题目大意
有一个n*m的地图，每个格子分为墙，空地和扣血的陷阱。求从起点到终点剩下血量的最大值
2.算法
①.30pts搜索
对于30%的数据，没有陷阱，我们就可以对整个图暴力搜索一遍，搜的到终点输出初始血量，否则输出-1。30pts到手！人人都爱TLE
②.100pts深搜+松弛
我们可以从起点做深搜，每当要进入一个点时，我们可以判断一下：如果我们新的方案比原来的优，那么更新，不然不进入该点。
突然，你发明了松弛。
代码如下（爆栈警告）
void dfs(int x,int y){
for(int k=0;k<4;k++){
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>m||mat[xx][yy]=='#')continue;
if(dis[xx][yy]>dis[x][y]+dam[mat[xx][yy]]){
dis[xx][yy]=dis[x][y]+dam[mat[xx][yy]];
dfs(xx,yy);
}
}
}
③.广搜+松弛
使用一个队列，每次进入一个点做松弛并加入队列，加队列，直到队列空了为止
代码：
void bfs()
{
queue<node>que;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=1e9;
dis[sx][sy]=0;
node z;
z.x=sx;z.y=sy;
que.push(z);
while(!que.empty())
{
int x=que.front().x,y=que.front().y;
for(int k=0;k<4;k++){
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>m||mat[xx][yy]=='#')continue;
if(dis[xx][yy]>dis[x][y]+dam[mat[xx][yy]]){
dis[xx][yy]=dis[x][y]+dam[mat[xx][yy]];
z.x=xx;z.y=yy;
que.push(z);
}
}
que.pop();
}
}
④.Bellman_Ford算法
考虑一种暴力的算法：我们可以重复枚举每一个点，对于每一个点，我们给上下左右进行松弛操作，直到没有一个点可以进行松弛为止。
代码：
void bellman_ford()
{
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=1e9;
dis[sx][sy]=0;
while(1)
{
bool flag=true;
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
for(int k=0;k<4;k++){
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>m||mat[xx][yy]=='#')continue;
if(dis[xx][yy]>dis[x][y]+dam[mat[xx][yy]])dis[xx][yy]=dis[x][y]+dam[mat[xx][yy]],flag=false;
}
if(flag)break;
}
}
恭喜你，你发明了Bellman_Ford算法。
⑤.SPFA
Bellman_Ford未免有点暴力，可以像广搜一样用队列优化一下
代码：
void SPFA()
{
queue<node>que;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=1e9;
dis[sx][sy]=0;
node z;
z.x=sx;z.y=sy;
que.push(z);
flag[sx][sy]=true;
while(!que.empty())
{
int x=que.front().x,y=que.front().y;flag[x][y]=false;
for(int k=0;k<4;k++){
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>m||mat[xx][yy]=='#')continue;
if(dis[xx][yy]>dis[x][y]+dam[mat[xx][yy]]){
if(!flag[xx][yy])
{
flag[xx][yy]=true;
z.x=xx;z.y=yy;
que.push(z);
}
dis[xx][yy]=dis[x][y]+dam[mat[xx][yy]];
}
}
que.pop();
}
}
⑥.Dijkstra
我们可以做循环遍历每个点，找出起点到该点血量损失最小的，并对上下左右松弛。
代码如下：
void dijkstra()
{
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=1e9;
dis[sx][sy]=0;
for(int i=1;i<=n*m;i++)
{
int mindis=1e9,minx,miny;
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
if(flag[x][y]==false&&mindis>dis[x][y])
{
mindis=dis[x][y];
minx=x;
miny=y;
}
if(mindis==1e9)break;
int x=minx,y=miny;
flag[x][y]=true;
for(int k=0;k<4;k++){
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>m||mat[xx][yy]=='#'||flag[xx][yy])continue;
if(dis[xx][yy]>dis[x][y]+dam[mat[xx][yy]])dis[xx][yy]=dis[x][y]+dam[mat[xx][yy]];
}
}
}
恭喜你，你又发明了Dijkstra算法。
3.总结
这一题有许多写法，但是都是从一开始的深搜广搜开始的。所以要先写最简单的写法，再一步步优化。