首页 > 代码库 > HDU2822 Dogs
HDU2822 Dogs
一般来说走一步不固定加上的权值的时候最好用优先队列,可以保证最优解;
做题目的时候先预先自己走一下路线,如果自己都不会走程序肯定写不出来的啦.
要好好分析走的过程,这样才可以一步到位;
1 #include<iostream> 2 #include<queue> 3 #define maxn 1005 4 int n,m; 5 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 6 int bx,by,ex,ey; 7 struct node 8 { 9 int x,y,t;10 friend bool operator <(node a,node b)//优先队列必须的11 {12 return a.t>b.t ;13 }14 }p,q;15 char map[maxn][maxn];16 bool visit[maxn][maxn];17 using namespace std;18 int bfs(int x,int y)19 {20 int i;21 priority_queue<node> game;22 p.x=x,p.y=y,p.t=0;23 game.push(p);24 visit[p.x][p.y]=true;25 while(!game.empty())26 {27 q=game.top();28 game.pop();29 if(q.x == ex && q.y == ey) return q.t;30 for(i=0;i<4;i++)31 {32 p.x=q.x+dir[i][0],p.y=q.y+dir[i][1],p.t=q.t;33 if(p.x<0 || p.x>=n || p.y<0 || p.y>=m || visit[p.x][p.y])//淘汰不满足条件的点34 continue;35 visit[p.x][p.y]=true;36 if(map[p.x][p.y]==‘.‘) p.t=q.t+1;//经过空地需要挖坑37 game.push(p);38 39 }40 }41 return -1;42 }43 int main()44 {45 int i;46 //freopen("2822.txt","r",stdin);47 while(~scanf("%d%d",&n,&m),n,m)48 {49 memset(visit,false,sizeof(visit));50 for(i=0;i<n;i++)51 52 scanf("%s",map+i);//比用cin快53 54 scanf("%d%d%d%d",&bx,&by,&ex,&ey);55 bx--,by--,ex--,ey--;//从0读入56 int t=bfs(bx,by);57 printf("%d\n",t);58 }59 return 0;60 }
HDU2822 Dogs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。