首页 > 代码库 > 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