这个题还没有敲 稍微看了一下别人的代码
觉得这个题太好了，特别有意思
题意就是 给一个矩阵有强 有敌人 有angel 有friends
friends可能有多个 但是hdu一个就能水过
我们还是按照正确的解法来考虑
r要到达a 中间可能会遇到x x是敌人 需要1单位时间去消灭
我们要求出最少的时间使得a被营救
那么r如果经过某一个点 消灭了一个敌人 就会有额外的时间
这样队列中 我们就不能只依靠顺序来bfs 了 而是依靠用时最少来bfs
但是多个r怎么解决？
这个逆向思维一下 从a出发看先遇到哪个r
这样下来这个思路就清楚了
开始敲
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=205;
char map[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
int xpos,ypos;//记录a的位置 也就是起点
int dir[4][2]={-1,0,1,0,0,-1,0,1};
struct Node
{
int x,y,time;
bool operator <(const Node & n)const
{
return time>n.time;
}
};
int bfs()
{
int i;
memset(vis,0,sizeof(vis));
Node node,no;
priority_queue<Node> pq;
node.x=xpos;
node.y=ypos;
node.time=0;
pq.push(node);
vis[node.x][node.y]=1;
while(!pq.empty())
{
node=pq.top();
pq.pop();
//printf("tanchuyici %d %d\n",node.x,node.y);
if(map[node.x][node.y]=='r')
return node.time;
for(i=0;i<4;++i)
{
no.x=node.x+dir[i][0];
no.y=node.y+dir[i][1];
if(vis[no.x][no.y]==0 && no.x>=0 && no.x<n && no.y>=0 &&no.y<m && map[no.x][no.y]!='#')
{
if(map[no.x][no.y]=='x')
no.time=node.time+2;
else
no.time=node.time+1;
vis[no.x][no.y]=1;
pq.push(no);
}
}
}
return -1;
}
int main()
{
int i,j,ans;
while(scanf("%d %d",&n,&m)!=EOF)
{
getchar();
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='a')
{
xpos=i;
ypos=j;
}
}
getchar();
}
ans=bfs();
if(ans==-1)
printf("Poor ANGEL has to stay in the prison all his life.\n");
else
printf("%d\n",ans);
}
return 0;
}