Advertisement
Guest User

Untitled

a guest
Jan 24th, 2020
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3. using namespace std;
  4. struct tCell{long long row, col;};
  5. queue<tCell> q;
  6. long long dist[257][257];
  7. long long n, m, s, t, u, x, y;
  8. void checker(long long r, long long c, long long prevr, long long prevc)
  9. {
  10. if (r<1||r>n||c<1||c>n||dist[r][c]!=0) return;
  11. q.push({r,c});
  12. dist[r][c]=dist[prevr][prevc]+1;
  13. }
  14. void bfs(tCell start, tCell finish)
  15. {
  16. tCell v;
  17. long long rr,cc;
  18. dist[start.row][start.col]=1;
  19. q.push(start);
  20. while(!q.empty())
  21. {
  22. v=q.front();
  23. q.pop();
  24. rr=v.row;
  25. cc=v.col;
  26. checker(rr-2, cc-1, rr, cc);
  27. checker(rr-2, cc+1, rr, cc);
  28. checker(rr+2, cc-1, rr, cc);
  29. checker(rr+2, cc+1, rr, cc);
  30. checker(rr-1, cc-2, rr, cc);
  31. checker(rr-1, cc+2, rr, cc);
  32. checker(rr+1, cc-2, rr, cc);
  33. checker(rr+1, cc+2, rr, cc);
  34. if (dist[finish.row][finish.col]>1) break;
  35. }
  36. }
  37. int main()
  38. {
  39. cin>>n>>m;
  40. cin>>s>>t>>u;
  41. while(u--)
  42. {
  43. cin>>x>>y;
  44. for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) dist[i][j]=0;
  45. tCell start = {x, y}, finish = {s, t};
  46. bfs(start, finish);
  47. if (dist[s][t]<1) cout<<"-1\n";
  48. else cout<<dist[s][t]-1<<"\n";
  49. }
  50. return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement