Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdlib.h>
- #include <stdio.h>
- #include <iostream>
- #include <math.h>
- #include <map>
- #include <set>
- #include <stack>
- #include <vector>
- #include <time.h>
- #include <random>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <queue>
- #include <deque>
- #include <functional>
- #include <cctype>
- #include <list>
- #define rt return
- #define rt0 return 0
- #define rt1 return 1
- #define mp make_pair
- #define cen cout << "\n"
- #define endl "\n"
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double db;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- const ll inf = 1000000009;
- const int sz = 310;
- char ar[sz][sz][sz];
- int n, w, h, xs = -1, ys;
- char dfs(int t, int x, int y){
- if (x < 0 || x >= w || y < 0 || y >= h || ar[t][x][y] == 2)
- rt 2;
- if (ar[t][x][y])
- rt ar[t][x][y];
- if (t == n - 1)
- rt ar[t][x][y] = 1;
- if (dfs(t + 1, x - 1, y) == 1)
- rt ar[t][x][y] = 1;
- if (dfs(t + 1, x + 1, y) == 1)
- rt ar[t][x][y] = 1;
- if (dfs(t + 1, x, y - 1) == 1)
- rt ar[t][x][y] = 1;
- if (dfs(t + 1, x, y + 1) == 1)
- rt ar[t][x][y] = 1;
- rt ar[t][x][y] = 2;
- }
- void df(int t, int x, int y){
- cout << x + 1 << " " << y + 1 << endl;
- if (ar[t + 1][x - 1][y] == 1)
- df(t + 1, x - 1, y);
- else if (ar[t + 1][x + 1][y] == 1)
- df(t + 1, x + 1, y);
- else if (ar[t + 1][x][y - 1] == 1)
- df(t + 1, x , y- 1);
- else if(ar[t + 1][x][y + 1] == 1)
- df(t + 1, x, y + 1);
- }
- int main(){
- freopen("broadcast.in", "r", stdin);
- freopen("broadcast.out", "w", stdout);
- cin >> w >> h >> n;
- for (int i = 0; i < n; ++i){
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- --x1; --x2; --y1; --y2;
- for (int j = x1; j <= x2; ++j){
- for (int k = y1; k <= y2; ++k){
- ar[i][j][k] = 2;
- }
- }
- }
- for (int j = 0; j < w; ++j){
- for (int k = 0; k < h; ++k){
- if (dfs(0, j, k) == 1){
- xs = j; ys = k;
- break;
- }
- }
- if (xs != -1)
- break;
- }
- if (xs == -1){
- cout << "Impossible";
- rt0;
- }
- df(0, xs, ys);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement