Advertisement
Guest User

Untitled

a guest
Aug 14th, 2019
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1e9;
  6.  
  7. int main() {
  8. int n, m, k, bx, by, ex, ey, nx, ny, w = 0;
  9. cin >> n >> m >> k >> bx >> by;
  10. vector <pair <int,int> > a(m);
  11. vector<pair <int, int> > res;
  12. for (int i = 0; i < m; ++i) {
  13. cin >> a[i].first >> a[i].second;
  14. }
  15. vector<int> dx = {-2, -1, 1, 2, 2, 1, -1, -2}, dy = {1, 2, 2, 1, -1, -2, -2, -1};
  16. vector<vector<int> > dist(n, vector<int>(n, INF));
  17. dist[bx][by] = 0;
  18. queue<pair<int, int> > q;
  19. q.push({bx, by});
  20. while (!q.empty()) {
  21. ex = q.front().first;
  22. ey = q.front().second;
  23. q.pop();
  24. for (int i = 0; i < 8; ++i) {
  25. if (ex + dx[i] < 0 || ey + dy[i] < 0 || ex + dx[i] >= n || ey + dy[i] >= n) continue;
  26. for(auto j : a){
  27. if(ex + dx[i] == j.first && ey + dy[i] == j.second) continue;
  28. }
  29. nx = ex + dx[i];
  30. ny = ey + dy[i];
  31. dist[nx][ny] = dist[ex][ey] + 1;
  32. if(dist[nx][ny] == k){
  33. res.push_back({nx, ny});
  34. }
  35. q.push({nx, ny});
  36. }
  37. }
  38. cout << res.size();
  39. for(auto i : res){
  40. cout << i.first << ' ' << i.second << endl;
  41. }
  42. return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement