Advertisement
Guest User

Untitled

a guest
Apr 24th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include<iostream>
  2. #include <vector>
  3. using namespace std;
  4. int main() {
  5.     int w, h, n;
  6.     cin >> w >> h >> n;
  7.     vector<vector<vector<bool>>> a(w+2, vector<vector<bool>>(h+2, vector<bool>(n+1, false)));
  8.     int x1, x2, y1, y2;
  9.     for (int j = 1; j <= w; j++) {
  10.         for (int k = 1; k <= h; k++) {
  11.             a[j][k][0] = true;
  12.         }
  13.     }
  14.    
  15.     for (int i = 1; i <= n; i++) {
  16.         cin >> x1 >> y1 >> x2 >> y2;
  17.        
  18.         for (int j = 1; j <= w; j++) {
  19.             for (int k = 1; k <= h; k++) {
  20.                 if ((a[j-1][k][n - 1] || a[j+1][k][n - 1] || a[j][k-1][n - 1] || a[j][k+1][n - 1]) && !(j>=x1 && j<=x2 && k>=y1 && k<=y2)) {
  21.                     a[j][k][n] = true;
  22.                 }
  23.             }
  24.         }
  25.    
  26.     }
  27.     bool q = true;
  28.     vector <pair<int, int>> ans(n);
  29.     for (int j = 1; j <= w; j++) {
  30.         for (int k = 1; k <= h; k++) {
  31.             cout << a[j][k][n] << ' ';
  32.             if (a[j][k][n]) {
  33.                 q = false;
  34.                 ans[n] = { j, k };
  35.                 break;
  36.             }
  37.         }
  38.         cout << endl;
  39.     }
  40.         if (q) {
  41.             cout << "Impossible";
  42.         }
  43.         else {
  44.             for (int i = n - 1; i >= 1; i--) {
  45.                 if (a[ans[i + 1].first-1][ans[i + 1].second][i]) {
  46.                     ans[i] = { ans[i + 1].first - 1, ans[i + 1].second };
  47.                 }
  48.                 else if (a[ans[i + 1].first+1][ans[i + 1].second][i]) {
  49.                     ans[i] = { ans[i + 1].first + 1, ans[i + 1].second };
  50.                 }
  51.                 else if (a[ans[i + 1].first][ans[i + 1].second-1][i]) {
  52.                     ans[i] = { ans[i + 1].first , ans[i + 1].second-1 };
  53.  
  54.                 }
  55.                 else if (a[ans[i + 1].first][ans[i + 1].second+1][i]) {
  56.                     ans[i] = { ans[i + 1].first , ans[i + 1].second+1 };
  57.                 }
  58.             }
  59.             for (int i = 1; i <= n; i++) {
  60.                 cout << ans[i].first << ' ' << ans[i].second << endl;
  61.             }
  62.         }
  63.        
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement