SHARE
TWEET

Untitled

a guest Oct 17th, 2018 103 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
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