Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define x1 sflsf
  6. #define y1 svjof
  7.  
  8. struct night{
  9. int x, y, x1, y1;
  10. };
  11.  
  12. night p[500];
  13.  
  14. int w, h, n, fx, fy;
  15.  
  16. pair < int, int > parent[400][400];
  17.  
  18. bool ok (int moment, int x, int y){
  19. if (moment >= n){
  20. fx = x;
  21. fy = y;
  22. return true;
  23. }
  24. //used[][]
  25. if (x + 1 <= w && (x + 1 <= p[moment].x || x + 1 >= p[moment].x1)){
  26. parent[x + 1][y] = make_pair(x, y);
  27. ok(moment + 1, x + 1, y);
  28. }
  29. if (x - 1 >= 1 && (x - 1 <= p[moment].x || x - 1 >= p[moment].x1)){
  30. parent[x - 1][y] = make_pair(x, y);
  31. ok(moment + 1, x - 1, y);
  32. }
  33. if (y + 1 <= h && (y + 1 <= p[moment].y || y + 1 >= p[moment].y1)){
  34. parent[x][y + 1] = make_pair(x, y);
  35. ok(moment + 1, x, y + 1);
  36. }
  37. if (y - 1 >= 1 && (y - 1 <= p[moment].y || y - 1 >= p[moment].y1)){
  38. parent[x][y - 1] = make_pair(x, y);
  39. ok(moment + 1, x, y - 1);
  40. }
  41. return false;
  42. }
  43.  
  44. void print(int sx, int sy) {
  45. vector < pair < int, int > > path;
  46. while (fx != sx && fy != sy){
  47. path.push_back(make_pair(fx, fy));
  48. fx = parent[fx][fy].first;
  49. fy = parent[fx][fy].second;
  50. }
  51. path.push_back(make_pair(sx, sy));
  52. reverse(path.begin(), path.end());
  53. for (int i = 1; i < path.size(); ++i)
  54. cout << path[i].first << ' ' << path[i].second << endl;
  55. }
  56.  
  57. int main(){
  58.  
  59. freopen("drone.in", "r", stdin);
  60.  
  61. ios_base::sync_with_stdio(0);
  62. cin.tie(0);
  63.  
  64. cin >> w >> h;
  65.  
  66. cin >> n;
  67.  
  68. for (int i = 1; i <= n; ++i){
  69. int a, b, a1, b1;
  70. cin >> a >> b >> a1 >> b1;
  71. p[i].x = a;
  72. p[i].y = b;
  73. p[i].x1 = a1;
  74. p[i].y1 = b1;
  75. }
  76. for (int i = 1; i <= w; ++i){
  77. for (int j = 1; j <= h; ++j){
  78. memset(p, 0, sizeof p);
  79. if(ok(1, i, j)){
  80. print(i, j);
  81. return 0;
  82. }
  83. }
  84. }
  85. cout << "Impossible";
  86. return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement