本文主要是介绍hdu1180（广搜+优先队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。
另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的
这是我的代码
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define eps 1e-9
#define N 25
#define P system("pause")
using namespace std;
int n,m;
int sx,sy,ex,ey;
int vis[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
char a[N][N];
struct node
{
int x,y,step;
friend bool operator<(node a,node b)
{
return a.step>b.step;
}
};
priority_queue<node> q;bool judge(int nx,int ny){
if(!vis[nx][ny]&&nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]!='*') return 1;
return 0;
}
int bfs()
{
node v;
while(!q.empty())
{
node u=q.top();
// cout<<u.x<<" "<<u.y<<" "<<u.step<<endl;
q.pop();
if(u.x==ex&&u.y==ey) return u.step;
for(int i=0;i<4;i++){
int nx=u.x+dx[i];
int ny=u.y+dy[i];
if(judge(nx,ny))
{
if( (a[nx][ny]=='-' && u.step%2==1) || (a[nx][ny]=='|' && u.step%2==0 ) )//
{
if((i==0||i==1)){
if(i==0) v.x=nx+1;
else if(i==1) v.x=nx-1;
v.y=ny;v.step=u.step+1;
if(judge(v.x,v.y)) {q.push(v);vis[v.x][v.y]=1;}
}
else{
v.x=u.x;v.y=u.y;v.step=u.step+1;
q.push(v);
}
continue;
}
if((a[nx][ny]=='-'&&u.step%2==0)||(a[nx][ny]=='|'&&u.step%2))
{
if((i==2||i==3)){
if(i==2) v.y=ny-1;
else if(i==3) v.y=ny+1;
v.x=nx;
v.step=u.step+1;
if(judge(v.x,v.y)) {q.push(v);vis[v.x][v.y]=1;}
}
else{
v.x=u.x;v.y=u.y;v.step=u.step+1;
q.push(v);
}
continue;
} //第三种情况
v.x=nx;v.y=ny;v.step=u.step+1;
q.push(v);
vis[nx][ny]=1;
}}
}
}int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);cc
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
while(!q.empty()) q.pop();
for(i=0;i<n;i++)
scanf("%s",a[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(a[i][j]=='S'){
sx=i;sy=j;
}
else if(a[i][j]=='T'){
ex=i;ey=j;
}
}
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
node temp;
temp.x=sx;temp.y=sy;temp.step=0;
q.push(temp);
cout<<bfs()<<endl;;}
//P;
return 0;
}这篇关于hdu1180（广搜+优先队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
