fork download
  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
stdin
1
5 5
S....
.....
.....
.....
....F
stdout
3