Advertisement
Guest User

Untitled

a guest
Jun 10th, 2016
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <iostream>
  5. #include <math.h>
  6. #include <map>
  7. #include <set>
  8. #include <stack>
  9. #include <vector>
  10. #include <time.h>
  11. #include <random>
  12. #include <algorithm>
  13. #include <string>
  14. #include <string.h>
  15. #include <queue>
  16. #include <deque>
  17. #include <functional>
  18. #include <cctype>    
  19. #include <list>
  20. #define rt return
  21. #define rt0 return 0
  22. #define rt1 return 1
  23. #define mp make_pair
  24. #define cen cout << "\n"
  25. #define endl "\n"
  26. using namespace std;
  27. typedef long long ll;
  28. typedef unsigned long long ull;
  29. typedef long double db;
  30. typedef pair<int, int> pii;
  31. typedef pair<ll, ll> pll;
  32. const ll inf = 1000000009;
  33. const int sz = 310;
  34. char ar[sz][sz][sz];
  35. int n, w, h, xs = -1, ys;
  36.  
  37. char dfs(int t, int x, int y){
  38.     if (x < 0 || x >= w || y < 0 || y >= h || ar[t][x][y] == 2)
  39.         rt 2;
  40.     if (ar[t][x][y])
  41.         rt ar[t][x][y];
  42.     if (t == n - 1)
  43.         rt ar[t][x][y] = 1;
  44.     if (dfs(t + 1, x - 1, y) == 1)
  45.         rt ar[t][x][y] = 1;
  46.     if (dfs(t + 1, x + 1, y) == 1)
  47.         rt ar[t][x][y] = 1;
  48.     if (dfs(t + 1, x, y - 1) == 1)
  49.         rt ar[t][x][y] = 1;
  50.     if (dfs(t + 1, x, y + 1) == 1)
  51.         rt ar[t][x][y] = 1;
  52.     rt ar[t][x][y] = 2;
  53. }
  54. void df(int t, int x, int y){
  55.     cout << x + 1 << " " << y + 1 << endl;
  56.     if (ar[t + 1][x - 1][y] == 1)
  57.         df(t + 1, x - 1, y);
  58.     else if (ar[t + 1][x + 1][y] == 1)
  59.         df(t + 1, x + 1, y);
  60.     else if (ar[t + 1][x][y - 1] == 1)
  61.         df(t + 1, x , y- 1);
  62.     else if(ar[t + 1][x][y + 1] == 1)
  63.         df(t + 1, x, y + 1);
  64.  
  65. }
  66. int main(){
  67.     freopen("broadcast.in", "r", stdin);
  68.     freopen("broadcast.out", "w", stdout);
  69.     cin >> w >> h >> n;
  70.     for (int i = 0; i < n; ++i){
  71.         int x1, y1, x2, y2;
  72.         cin >> x1 >> y1 >> x2 >> y2;
  73.         --x1; --x2; --y1; --y2;
  74.         for (int j = x1; j <= x2; ++j){
  75.             for (int k = y1; k <= y2; ++k){
  76.                 ar[i][j][k] = 2;
  77.             }
  78.         }
  79.     }
  80.     for (int j = 0; j < w; ++j){
  81.         for (int k = 0; k < h; ++k){
  82.             if (dfs(0, j, k) == 1){
  83.                 xs = j; ys = k;
  84.                 break;
  85.             }
  86.         }
  87.         if (xs != -1)
  88.             break;
  89.     }
  90.     if (xs == -1){
  91.         cout << "Impossible";
  92.         rt0;
  93.     }
  94.     df(0, xs, ys);
  95.  
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement