SHARE
TWEET

Zeta and Thanos

AlaminSakib Dec 8th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int n, m;
  5. struct data
  6. {
  7.     int why, ex;
  8. };
  9.  
  10. int bfs(int levels[1010][1010], bool vis[1010][1010], char arr[1010][1010], int siz, int x, int y, int tx, int ty)
  11. {
  12.     int pntr = -1;
  13.     struct data d[siz];
  14.     pntr++;
  15.     d[pntr].why = y;
  16.     d[pntr].ex = x;
  17.     vis[y][x] = true;
  18.     levels[y][x] = 0;
  19.     while(pntr >= 0)
  20.     {
  21.         struct data temp = d[pntr];
  22.         pntr--;
  23.         int sy = temp.why;
  24.         int sx = temp.ex;
  25.         if(isalpha(arr[sy + 1][sx])) cout << "sakib";
  26.         if(sy + 1 && sx && sy + 1 <= n && sx <= m && isalnum(arr[sy + 1][sx]) && !vis[sy + 1][sx] && arr[sy + 1][sx] != '*')
  27.         {
  28.             vis[sy + 1][sx] = true;
  29.             pntr++;
  30.             d[pntr].why = sy + 1;
  31.             d[pntr].ex = sx;
  32.             levels[sy + 1][sx] = levels[sy][sx] + 1;
  33.             if(sy + 1 == ty && sx == tx) return levels[sy + 1][sx];
  34.         }
  35.         if(sy - 1 && sx && sy - 1 <= n && sx <= m && isalnum(arr[sy - 1][sx]) && !vis[sy - 1][sx] && arr[sy - 1][sx] != '*')
  36.         {
  37.             vis[sy - 1][sx] = true;
  38.             pntr++;
  39.             d[pntr].why = sy - 1;
  40.             d[pntr].ex = sx;
  41.             levels[sy - 1][sx] = levels[sy][sx] + 1;
  42.             if(sy - 1 == ty && sx == tx) return levels[sy - 1][sx];
  43.         }
  44.         if(sy && sx + 1 && sy <= n && sx + 1 <= m && isalnum(arr[sy][sx + 1]) && !vis[sy][sx + 1] && arr[sy][sx + 1] != '*')
  45.         {
  46.             vis[sy][sx + 1] = true;
  47.             pntr++;
  48.             d[pntr].why = sy;
  49.             d[pntr].ex = sx + 1;
  50.             levels[sy][sx + 1] = levels[sy][sx] + 1;
  51.             if(sy == ty && sx + 1 == tx) return levels[sy][sx + 1];
  52.         }
  53.         if(sy && sx - 1 && sy <= n && sx - 1 <= m && isalnum(arr[sy][sx - 1]) && !vis[sy][sx - 1] && arr[sy][sx - 1] != '*')
  54.         {
  55.             vis[sy][sx - 1] = true;
  56.             pntr++;
  57.             d[pntr].why = sy;
  58.             d[pntr].ex = sx - 1;
  59.             levels[sy][sx - 1] = levels[sy][sx] + 1;
  60.             if(sy == ty && sx - 1 == tx) return levels[sy][sx - 1];
  61.         }
  62.     }
  63.     return -1;
  64. }
  65.  
  66. int main()
  67. {
  68.     char arr[1010][1010];
  69.     int x, y, q;
  70.     cin >> n >> m;
  71.     for(int i = 1; i <= n; i++)
  72.     {
  73.         for(int j = 1; j <= m; j++)
  74.         {
  75.             cin >> arr[i][j];
  76.         }
  77.     }
  78.     cin >> x >> y;
  79.     cin >> q;
  80.     while(q--)
  81.     {
  82.         bool vis[1010][1010] = {false};
  83.         int levels[1010][1010] = {0};
  84.         int tx, ty;
  85.         cin >> tx >> ty;
  86.         if(arr[ty][tx] == '*')
  87.         {
  88.             cout << -1 << " " << -1 << endl;
  89.             continue;
  90.         }
  91.         int distance = bfs(levels, vis, arr, n * m, x, y, tx, ty);
  92.         if(distance == -1) cout << -1 << " " << -1 << endl;
  93.         else cout << distance << "something" << endl;       //edit here
  94.     }
  95.     return 0;
  96. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top