G2A Many GEOs
SHARE
TWEET

Untitled

a guest Oct 17th, 2018 141 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
Ledger Nano X - The secure hardware wallet
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