AlaminSakib

Zeta and Thanos

Dec 8th, 2019
91
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