题目链接：Rescue
进度落下的太多了，哎╮(╯▽╰)╭，渣渣我总是埋怨进度比别人慢。。。为什么不试着改变一下捏。。。。
開始以为是水题，想敲一下练手的，后来发现并非一个简单的搜索题，BFS做肯定出事。。。后来发现题目里面也有坑
题意是从r到a的最短距离，“.”相当时间单位1，“x”相当时间单位2，求最短时间
HDU 搜索课件上说，这题和HDU1010相似，刚開始并没有认为像剪枝，就改用 双向BFS 0ms 一Y，爽！
网上查了一下，神牛们居然用BFS+优先队列。。。顿悟
那么本题的搜索树能够理解为root 为a，连接若干枝条，枝条的叶子就是r，那么深度大的枝条剪枝，深度最小的自然就是答案；用优先队列来控制过滤深度较大枝条，进行剪枝。
敲了一下，BFS + 优先队列 15ms 一Y，相信假设在ans的存储上优化一下，把较小的ans优先储存，0ms非常轻松
送一特殊数据：
3 3
.a.
x#.
.r.
打印 4
BFS + 优先队列 代码例如以下
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
const int N = 210;
using namespace std; struct node
{
int x, y,ans;
friend bool operator <(const node &a,const node &b)
{
return a.ans>b.ans;
}
};
int n, m;
char ma[N][N];
bool vis[N][N];
int sx, sy;
int mv[4][2] = {{-1,0},{0,1},{0,-1},{1,0}}; void BFS(int sx,int sy)
{
priority_queue<node> q;
node f, t;
f.x = sx, f.y = sy, f.ans = 0;
vis[sx][sy] = true;
q.push(f);
while(!q.empty())
{
t = q.top();
if(ma[t.x][t.y]=='r')
{
cout<<t.ans<<endl;
return ;
}
q.pop();
for(int i=0; i<4; i++)
{
f.x = t.x +mv[i][0];
f.y = t.y +mv[i][1];
if(!vis[f.x][f.y]&&0<=f.x&&f.x<n&&0<=f.y&&f.y<m&&ma[f.x][f.y]!='#')
{
if(ma[f.x][f.y]=='x')
{
f.ans = t.ans+2;
q.push(f);
}
else
{
f.ans = t.ans+1;
q.push(f);
}
vis[f.x][f.y] = true;
}
}
}
cout<<"Poor ANGEL has to stay in the * all his life."<<endl;
} int main()
{
while(~scanf("%d%d",&n,&m))
{
bool flag = 0;
for(int i=0; i<n; i++)
{
scanf("%s",ma[i]);
if(flag)
continue;
for(int j=0; j<m; j++)
{
if(ma[i][j]=='a')
{
sx=i;sy=j;flag = true;
break;
} }
}
memset(vis,0,sizeof(vis));
BFS(sx,sy);
}
return 0;
}
双向BFS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
const int N = 210;
using namespace std;
int mapp[N][N];
int vis[N][N];
struct node{
int x,y;
};
int n,m;
char ma[210][210];
int mv[4][2] = {{1,0},{0,1},{0,-1},{-1,0}};
int dis[N][N];
void BFS(int sx,int sy,int ex,int ey)
{ queue<node>q;
node t,f;
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
f.x = sx; f.y = sy;
t.x = ex; t.y = ey;
vis[sx][sy] = 1;
vis[ex][ey] = 2;
q.push(f);
q.push(t);
while(!q.empty())
{
t = q.front();
q.pop();
for(int i = 0;i<4;i++)
{
f.x = t.x + mv[i][0];
f.y = t.y + mv[i][1];
if(0<=f.x && f.x <n && 0<=f.y && f.y<m)
{
if(ma[f.x][f.y]=='#') continue ;
if(!vis[f.x][f.y]&& ma[f.x][f.y]=='x')
{
dis[f.x][f.y] = dis[t.x][t.y] + 2;
q.push(f);
vis[f.x][f.y] = vis[t.x][t.y];
}
else if(!vis[f.x][f.y]&& ma[f.x][f.y]=='.')
{
dis[f.x][f.y] = dis[t.x][t.y] + 1;
q.push(f);
vis[f.x][f.y] = vis[t.x][t.y];
}
else if(vis[f.x][f.y]!=vis[t.x][t.y])
{
printf("%d\n",dis[f.x][f.y]+dis[t.x][t.y] + 1);
return ;
}
}
}
}
cout<<"Poor ANGEL has to stay in the * all his life."<<endl;
}
int main()
{
int t,sx,sy,ex,ey;
while(~scanf("%d%d",&n,&m))
{
for(int i = 0;i<n;i++)
{
scanf("%s",ma[i]);
for(int j = 0;j<m;j++)
{
if(ma[i][j] == 'a')
{
sx = i; sy = j;
}
else if(ma[i][j]=='r')
{
ex = i; ey = j;
}
}
}
BFS(sx,sy,ex,ey);
}
return 0;
}
渣渣