Sicily_How can I go-白红宇

Sicily_How can I go

阅读量：6856 次

发布时间：2019-06-26

本文共 1320 字，大约阅读时间需要 4 分钟。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define LL long longbool vis[1005][1005];int go[3][2]= { { 1,1},{-1,1},{ 0,1}};int n,L[1005],R[1005];struct point{ int x,y,steps,dis; friend bool operator< (point n1, point n2) //优先队列的比较函数，按照steps的大小从小到大排列排列队列中元素 { return n1.steps > n2.steps; } point(int a,int b,int c,int d) { x=a,y=b,steps=c,dis=d; }};int bfs(int hehe){ priority_queue
            
              Q; //优先队列 point f(hehe,0,0,n); Q.push(f); vis[hehe][0]=1; while(!Q.empty()) { point s=Q.top(); Q.pop(); for(int i=0;i<3;++i) { int nx=s.x+go[i][0]; int ny=s.y+go[i][1]; int d=abs(ny-n); if(vis[nx][ny]||nx
             
              L[ny]||abs(ny-n)>=s.dis) //abs(ny-n)>=s.dis剪枝，如果s.dis大于终点和ny的值就不需要加入队列中了 continue; if(ny==n) { return s.steps; //为啥是return s.steps呢，因为有一个方向是（x,y+1)，也就是对每个点来说，它的下一个Y坐标必有不需要增加花费的X坐标 } vis[nx][ny]=1; point next(nx,ny,s.steps+(i!=2),d); //i==2的方向是不需要增加1的，其他都是需要增加的 Q.push(next); } } return -1;}int main(){ int t,i,s_x; cin>>t; while(t--) { scanf("%d",&n); for(i=1;i<=n;++i) scanf("%d",&L[i]); for(i=1;i<=n;++i) scanf("%d",&R[i]); memset(vis,0,sizeof(vis)); scanf("%d",&s_x); printf("%d\n",bfs(s_x)); } return 0;}