fork(1) download
copy 
  1. /******************************************************************
  2.  *                   BISMIintAHIR RAHMANIR RAHIM                   *
  3.  *                     Saddam Hossain shishir                     *
  4.  *       Hajee Mohammad Danesh Science & Technology University    *
  5.  *                                                                *
  6.  ***************************************************************** */
  7. #include<bits/stdc++.h>
  8.  
  9. #define all(v) v.begin(),v.end()
  10. #define sc scanf
  11. #define si(t) scanf("%d",&t)
  12. #define sl(t) scanf("%I64d",&t)
  13.  
  14. #define sii(a,b) scanf("%d%d",&a,&b)
  15.  
  16. #define pt(a) printf("%d\n",a)
  17. #define PLN(a) printf("%I64d\n",a)
  18. #define pf printf
  19.  
  20. #define gcd(a,b) __gcd(a,b)
  21. #define ff first
  22. #define ss second
  23.  
  24. #define pb push_back
  25. #define pii pair<int,int>
  26. #define mp make_pair
  27. #define pi acos(-1.0)
  28. #define PI 3.1415926535897932385
  29. #define Sin(a) sin((pi*a)/180)
  30. #define siz 3000001
  31. #define mem(ar) memset(ar,0,sizeof ar)
  32. #define one(x) __builtin_popcount(x)
  33. #define mod 100000009
  34. #define faster ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  35. typedef long long ll;
  36.  
  37. using namespace std;
  38.  
  39. //int dx[]= {-1,-1,0,0,1,1};
  40. //int dy[]= {-1,0,-1,1,0,1};
  41. //int dx[]= {0,0,1,-1};/*4 side move*/
  42. //int dy[]= {-1,1,0,0};/*4 side move*/
  43. int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
  44. int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
  45. //int dx[]= {1,1,2,2,-1,-1,-2,-2}; /*knight move*/
  46. //int dy[]= {2,-2,1,-1,2,-2,1,-1}; /*knight move*/
  47.  
  48. //'A'=65,'Z'=90 'a'=97 'z'=122 '0'=48
  49.  
  50.  
  51. //upper bound and lower bound
  52.  
  53. #define LB(a,value) (lower_bound(all(a),value)-a.begin())
  54. #define UB(a,value) (upper_bound(all(a),value)-a.begin())
  55. //S.insert(lower_bound(S.begin( ),S.end( ),x),x); //S is vector
  56.  
  57. int Set(int N,int pos)
  58. {
  59.     return N=N | (1<<pos);
  60. }
  61. int reset(int N,int pos)
  62. {
  63.     return N= N & ~(1<<pos);
  64. }
  65. bool check(int N,int pos)
  66. {
  67.     return (bool)(N & (1<<pos));
  68. }
  69. /* -a%b---------
  70. ll  Mod(ll  a,ll  b)
  71. {
  72.     ll  c = a % b;
  73.     return (c < 0) ? c + b : c;
  74. }
  75. /*
  76. ll  power(ll num,ll p)
  77. {
  78.     int i;
  79.     ll sum=1;
  80.     for(i=1; i<=p; i++)
  81.         sum*=num;
  82.     return sum;
  83. }
  84. */
  85. int dis[1004][1005],vis[1004][1004];
  86.  
  87. int row,col;
  88. void bfs(int sx,int sy)
  89. {
  90.     int j,r;
  91.     vis[sx][sy]=1;
  92.     queue<pii>q;
  93.     q.push(pii(sx,sy));
  94.     while(!q.empty())
  95.     {
  96.         pii top=q.front();
  97.         q.pop();
  98.         j=r=0;
  99.         for(int k=0; k<8; k++)
  100.         {
  101.             int tx=top.ff+dx[k];
  102.             int ty=top.ss+dy[k];
  103.             if(tx>=1&&tx<=row &&ty>=1 &&ty<=col&&vis[tx][ty]==0)
  104.             {
  105.                 vis[tx][ty]=1;
  106.                 dis[tx][ty]=dis[top.ff][top.ss]+1;
  107.                 q.push(pii(tx,ty));
  108.             }
  109.         }
  110.     }
  111. }
  112. char ch;
  113. int main()
  114. {
  115.     int x,ro1,co1,ro2,co2,i,j,t;
  116.     char c1,c2;
  117.     si(t);
  118.     while(t--)
  119.     {
  120.         memset(vis,0,sizeof vis);
  121.         mem(dis);
  122.         si(row),si(col);
  123.         for(i=1; i<=row; i++)
  124.         {
  125.             for(j=1; j<=col; j++)
  126.             {
  127.                 scanf(" %c",&ch);
  128.                 if(ch=='S')
  129.                 {
  130.                     ro1=i;
  131.                     co1=j;
  132.                 }
  133.                 else if(ch=='F')
  134.                 {
  135.                     ro2=i;
  136.                     co2=j;
  137.                 }
  138.                 else if(ch=='X')
  139.                 {
  140.                     vis[i][j]=1;
  141.                 }
  142.             }
  143.         }
  144.         bfs(ro1,co1);
  145.         printf("%d\n",dis[ro2][co2]-1);
  146.     }
  147.     return 0;
  148. }
Success #stdin #stdout 0s 23112KB
comments (?)
stdin
copy 
1
5 5
S....
.....
.....
.....
....F
stdout
copy 
3
https://ideone.com/uU7cYY
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!