Guest User

Untitled

a guest
Oct 17th, 2018
176
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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];
  86. char str[1001][1001];
  87. int vis[1001][1001][4];
  88. int row,col,ro2,co2;
  89. void bfs(int sx,int sy)
  90. {
  91. int x,y,i,dir;
  92. vis[sx][sy][1]=1;
  93. vis[sx][sy][2]=1;
  94. vis[sx][sy][3]=1;
  95. vis[sx][sy][4]=1;
  96. dis[sx][sy]=1;
  97. queue<pii>q;
  98. q.push(pii(sx,sy));
  99. while(!q.empty())
  100. {
  101. pii top=q.front();
  102. q.pop();
  103. x=top.ff;
  104. y=top.ss;
  105. if(x==ro2 and y==co2) break;
  106. // cout<<x<<" "<<y<<endl;
  107. // cout<<"dis="<<dis[x][y]<<endl;
  108. dir=1;
  109. //right
  110. for(i=y+1; i<=col; i++)
  111. {
  112. if(str[x][i]=='X') break;
  113. if(vis[x][i][dir]==1) break;
  114. if(dis[x][i]==0)
  115. {
  116. dis[x][i]=dis[x][y]+1;
  117. vis[x][i][dir]=1;
  118. // cout<<x<<" one "<<i<<endl;
  119. q.push(pii(x,i));
  120. }
  121. }
  122. //left
  123. for(i=y-1; i>=1; i--)
  124. {
  125. if(str[x][i]=='X') break;
  126. if(vis[x][i][dir]==1) break;
  127. if(dis[x][i]==0)
  128. {
  129. dis[x][i]=dis[x][y]+1;
  130. vis[x][i][dir]=1;
  131. // cout<<x<<" 4th "<<i<<endl;
  132. q.push(pii(x,i));
  133. }
  134. }
  135. dir++;
  136. //cout<<endl;
  137. //down
  138. for(i=x+1; i<=row; i++)
  139. {
  140. if(str[i][y]=='X') break;
  141. if(vis[i][y][dir]==1) break;
  142. if(dis[i][y]==0)
  143. {
  144. dis[i][y]=dis[x][y]+1;
  145. vis[i][y][dir]=1;
  146. // cout<<i<<" 2nd "<<y<<endl;
  147. q.push(pii(i,y));
  148. }
  149. }
  150. // cout<<endl;
  151. //up
  152. // dir++;
  153. for(i=x-1; i>=1; i--)
  154. {
  155. if(str[i][y]=='X') break;
  156. if(vis[i][y][dir]==1) break;
  157. if(dis[i][y]==0)
  158. {
  159. dis[i][y]=dis[x][y]+1;
  160. vis[i][y][dir]=1;
  161. // cout<<i<<" 3rd "<<y<<endl;
  162. q.push(pii(i,y));
  163. }
  164. }
  165.  
  166. // cout<<endl;
  167. // dir++;
  168. //right up
  169. int yy;
  170. yy=y;
  171. dir++;
  172. for(i=x-1; i>=1; i--)
  173. {
  174. yy++;
  175. if(yy>col) break;
  176. if(str[i][yy]=='X') break;
  177. if(vis[i][yy][dir]==1) break;
  178. if(dis[i][yy]==0)
  179. {
  180. dis[i][yy]=dis[x][y]+1;
  181. vis[i][yy][dir]=1;
  182. q.push(pii(i,yy));
  183. // cout<<i<<" 5th "<<yy<<endl;
  184. }
  185. }
  186. yy=y;
  187. //left down
  188. // dir++;
  189. for(i=x+1; i<=row; i++)
  190. {
  191. yy--;
  192. if(yy<=0) break;
  193. if(str[i][yy]=='X') break;
  194. if(vis[i][yy][dir]==1) break;
  195. if(dis[i][yy]==0)
  196. {
  197. dis[i][yy]=dis[x][y]+1;
  198. vis[i][yy][dir]=1;
  199. q.push(pii(i,yy));
  200. // cout<<i<<" 7th "<<yy<<endl;
  201. }
  202. }
  203.  
  204. int xx;
  205. xx=x;
  206. yy=y;
  207. //right down
  208. // cout<<endl;
  209. dir++;
  210. for(i=xx+1; i<=row; i++)
  211. {
  212. yy++;
  213. if(yy>col) break;
  214. if(str[i][yy]=='X') break;
  215. if(vis[i][yy][dir]==1) break;
  216. if(dis[i][yy]==0)
  217. {
  218. dis[i][yy]=dis[x][y]+1;
  219. vis[i][yy][dir]=1;
  220. q.push(pii(i,yy));
  221. // cout<<i<<" 6th "<<yy<<endl;
  222. }
  223. }
  224. yy=y;
  225. //left up
  226. for(i=x-1; i>=1; i--)
  227. {
  228. yy--;
  229. if(yy<=0) break;
  230. if(str[i][yy]=='X') break;
  231. if(vis[i][yy][dir]==1) break;
  232. if(dis[i][yy]==0)
  233. {
  234. dis[i][yy]=dis[x][y]+1;
  235. vis[i][yy][dir]=1;
  236. q.push(pii(i,yy));
  237. // cout<<i<<" 8th "<<yy<<endl;
  238. }
  239. }
  240. }
  241. }
  242. char ch,lol;
  243. int main()
  244. {
  245. int x,ro1,co1,i,j,t;
  246. char c1,c2;
  247. si(t);
  248. while(t--)
  249. {
  250. mem(dis);
  251. mem(vis);
  252. si(row),si(col);
  253. for(i=1; i<=row; i++)
  254. {
  255. for(j=1; j<=col; j++)
  256. {
  257. scanf(" %c",&ch);
  258. if(ch=='S')
  259. {
  260. ro1=i;
  261. co1=j;
  262. }
  263. else if(ch=='F')
  264. {
  265. ro2=i;
  266. co2=j;
  267. }
  268. str[i][j]=ch;
  269. }
  270. }
  271. bfs(ro1,co1);
  272. printf("%d\n",dis[ro2][co2]-1);
  273. }
  274. return 0;
  275. }
  276. /*
  277. 1
  278. 5 5
  279. S....
  280. .....
  281. .....
  282. .....
  283. ....F
  284. */
RAW Paste Data