SHARE
TWEET

QUEEN - Wandering Queen

a guest Oct 18th, 2018 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define sz 1005
  3. using namespace std;
  4. const int dx[]= {1,1,0,-1,-1,-1,0,1};
  5. const int dy[]= {0,1,1,1,0,-1,-1,-1};
  6. struct node
  7. {
  8.     int x,y,dir,mov;
  9.     node()
  10.     {
  11.         x=y=mov=0;
  12.         dir=-1;
  13.     }
  14. };
  15. char str[sz][sz];
  16. int vis[sz][sz];
  17. int n,m;
  18. queue<node> qq;
  19. int bfs(node S,node F)
  20. {
  21.     int i,j,k,l,row,col,mn,cost;
  22.     bool key;
  23.     mn=INT_MAX;
  24.     vis[S.x][S.y]=0;
  25.     qq.push(S);
  26.     node uu,vv;
  27.     key=false;
  28.     while(!qq.empty())
  29.     {
  30.         uu=qq.front();
  31.         qq.pop();
  32.         for(i=0; i<8; i++)
  33.         {
  34.             row=dx[i]+uu.x;
  35.             col=dy[i]+uu.y;
  36.             if(uu.dir==-1)     cost=1;
  37.             else if(uu.dir!=i)
  38.             {
  39.                 cost=uu.mov+1;
  40.             }
  41.             else
  42.             {
  43.                 cost = uu.mov;
  44.             }
  45.             if((row>=1 && row<=n) &&(col>=1 && col<=m) && str[row][col]!='X' && cost<=vis[row][col])
  46.             {
  47.  
  48.                 if(row==F.x and col==F.y)
  49.                 {
  50.                     vis[row][col]=cost;
  51.                     key=true;
  52.                 }
  53.                 else
  54.                 {
  55.                     vis[row][col]=cost;
  56.                     vv.x=row;
  57.                     vv.y=col;
  58.                     vv.dir=i;
  59.                     vv.mov=cost;
  60.                     qq.push(vv);
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     if(key) return vis[F.x][F.y];
  66.     return -1;
  67. }
  68. int main()
  69. {
  70.     int i,tt,j,k,l,rec,store,now,pore,baki;
  71.     node S,F;
  72.     int tx,ty,sx,sy;
  73.     char ch;
  74.     scanf("%d",&tt);
  75.     getchar();
  76.     while(tt--)
  77.     {
  78.         memset(vis,20,sizeof(vis));
  79.         scanf("%d %d",&n,&m);
  80.         getchar();
  81.         for(i=1; i<=n; i++)
  82.         {
  83.             for(j=1; j<=m; j++)
  84.             {
  85.                 ch=getchar();
  86.                 if(ch=='S')
  87.                 {
  88.                     sx=i,sy=j;
  89.                 }
  90.                 if(ch=='F')
  91.                 {
  92.                     tx=i,ty=j;
  93.                 }
  94.                 str[i][j]=ch;
  95.             }
  96.             getchar();
  97.         }
  98.         if(n==1 && m==1){
  99.             printf("-1\n");
  100.             continue;
  101.         }
  102.         S.x=sx;
  103.         S.y=sy;
  104.         S.mov=0;
  105.         S.dir=-1;
  106.  
  107.         F.x=tx;
  108.         F.y=ty;
  109.  
  110.         printf("%d\n",bfs(S,F));
  111.         while(!qq.empty()) qq.pop();
  112.     }
  113.     return 0;
  114. }
  115.  
  116.  
  117. /*
  118. 3
  119. 3 3
  120. S..
  121. ...
  122. ..F
  123. 3 3
  124. S..
  125. XX.
  126. F..
  127. 3 3
  128. S..
  129. XXX
  130. ..F
  131.  
  132.  
  133. 6
  134. 2 2
  135. SF
  136. ..
  137. 2 2
  138. S.
  139. F.
  140. 2 2
  141. S.
  142. .F
  143. 2 2
  144. SX
  145. XF
  146.  
  147. 1
  148. 5 5
  149. SF...
  150. .X.X.
  151. ...X.
  152. .X...
  153. X...X
  154.  
  155.  
  156. 1
  157. 3 4
  158. S...
  159. XXX.
  160. XFXX
  161. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top