SHARE
TWEET

SPOJ: QUEEN — Wandering Queen(2nd Edition)

a guest Oct 18th, 2018 82 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][10];
  17. int dis[sz][sz];
  18. int n,m;
  19. queue<node> qq;
  20. int bfs(node S,node F)
  21. {
  22.     int i,j,k,l,row,col,mn,cost;
  23.     bool key;
  24.     mn=INT_MAX;
  25.     vis[S.x][S.y][0]=0;
  26.     vis[S.x][S.y][1]=0;
  27.     vis[S.x][S.y][2]=0;
  28.     vis[S.x][S.y][3]=0;
  29.     vis[S.x][S.y][4]=0;
  30.     vis[S.x][S.y][5]=0;
  31.     vis[S.x][S.y][6]=0;
  32.     vis[S.x][S.y][7]=0;
  33.     dis[S.x][S.y]=0;
  34.     qq.push(S);
  35.     node uu,vv;
  36.     key=false;
  37.     while(!qq.empty())
  38.     {
  39.         uu=qq.front();
  40.         qq.pop();
  41.         for(i=0; i<8; i++)
  42.         {
  43.             row=dx[i]+uu.x;
  44.             col=dy[i]+uu.y;
  45.             if(uu.dir==-1)     cost=1;
  46.             else if(uu.dir!=i)
  47.             {
  48.                 cost=uu.mov+1;
  49.             }
  50.             else
  51.             {
  52.                 cost = uu.mov;
  53.             }
  54.             if((row>=1 && row<=n) &&(col>=1 && col<=m) && str[row][col]!='X' && cost<=vis[row][col][i])
  55.             {
  56.  
  57.                 if(row==F.x and col==F.y)
  58.                 {
  59.                     vis[row][col][i]=min(vis[row][col][i],cost);
  60.                     dis[row][col]=min(dis[row][col],vis[row][col][i]);
  61.                     key=true;
  62.                 }
  63.                 else
  64.                 {
  65.                     vis[row][col][i]=min(vis[row][col][i],cost);
  66.                     dis[row][col]=min(dis[row][col],vis[row][col][i]);
  67.                     vv.x=row;
  68.                     vv.y=col;
  69.                     vv.dir=i;
  70.                     vv.mov=cost;
  71.                     qq.push(vv);
  72.                 }
  73.             }
  74.         }
  75.     }
  76.     if(key) return dis[F.x][F.y];
  77.     return -1;
  78. }
  79. int main()
  80. {
  81.     int i,tt,j,k,l,rec,store,now,pore,baki;
  82.     node S,F;
  83.     int tx,ty,sx,sy;
  84.     char ch;
  85.     scanf("%d",&tt);
  86.     getchar();
  87.     while(tt--)
  88.     {
  89.         memset(vis,20,sizeof(vis));
  90.         memset(dis,20,sizeof(dis));
  91.         //printf("vis = %d\n",vis[56][78]);
  92.         scanf("%d %d",&n,&m);
  93.         getchar();
  94.         for(i=1; i<=n; i++)
  95.         {
  96.             for(j=1; j<=m; j++)
  97.             {
  98.                 ch=getchar();
  99.                 if(ch=='S')
  100.                 {
  101.                     sx=i,sy=j;
  102.                 }
  103.                 if(ch=='F')
  104.                 {
  105.                     tx=i,ty=j;
  106.                 }
  107.                 str[i][j]=ch;
  108.             }
  109.             getchar();
  110.         }
  111.         if(n==1 && m==1){
  112.             printf("-1\n");
  113.             continue;
  114.         }
  115.         S.x=sx;
  116.         S.y=sy;
  117.         S.mov=0;
  118.         S.dir=-1;
  119.  
  120.         F.x=tx;
  121.         F.y=ty;
  122.  
  123.         printf("%d\n",bfs(S,F));
  124.         while(!qq.empty()) qq.pop();
  125.     }
  126.     return 0;
  127. }
  128.  
  129.  
  130. /*
  131. 3
  132. 3 3
  133. S..
  134. ...
  135. ..F
  136. 3 3
  137. S..
  138. XX.
  139. F..
  140. 3 3
  141. S..
  142. XXX
  143. ..F
  144.  
  145.  
  146. 6
  147. 2 2
  148. SF
  149. ..
  150. 2 2
  151. S.
  152. F.
  153. 2 2
  154. S.
  155. .F
  156. 2 2
  157. SX
  158. XF
  159.  
  160. 1
  161. 5 5
  162. SF...
  163. .X.X.
  164. ...X.
  165. .X...
  166. X...X
  167.  
  168.  
  169. 1
  170. 3 4
  171. S...
  172. XXX.
  173. XFXX
  174.  
  175. 1
  176. 4 4
  177. S...
  178. ....
  179. ....
  180. ...F
  181.  
  182. 1
  183. 5 6
  184. ...F..
  185. ..XX..
  186. .XSX..
  187. ...XX.
  188. ......
  189. */
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