Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define x1 sflsf
- #define y1 svjof
- struct night{
- int x, y, x1, y1;
- };
- night p[500];
- int w, h, n, fx, fy;
- pair < int, int > parent[400][400];
- bool ok (int moment, int x, int y){
- if (moment >= n){
- fx = x;
- fy = y;
- return true;
- }
- //used[][]
- if (x + 1 <= w && (x + 1 <= p[moment].x || x + 1 >= p[moment].x1)){
- parent[x + 1][y] = make_pair(x, y);
- ok(moment + 1, x + 1, y);
- }
- if (x - 1 >= 1 && (x - 1 <= p[moment].x || x - 1 >= p[moment].x1)){
- parent[x - 1][y] = make_pair(x, y);
- ok(moment + 1, x - 1, y);
- }
- if (y + 1 <= h && (y + 1 <= p[moment].y || y + 1 >= p[moment].y1)){
- parent[x][y + 1] = make_pair(x, y);
- ok(moment + 1, x, y + 1);
- }
- if (y - 1 >= 1 && (y - 1 <= p[moment].y || y - 1 >= p[moment].y1)){
- parent[x][y - 1] = make_pair(x, y);
- ok(moment + 1, x, y - 1);
- }
- return false;
- }
- void print(int sx, int sy) {
- vector < pair < int, int > > path;
- while (fx != sx && fy != sy){
- path.push_back(make_pair(fx, fy));
- fx = parent[fx][fy].first;
- fy = parent[fx][fy].second;
- }
- path.push_back(make_pair(sx, sy));
- reverse(path.begin(), path.end());
- for (int i = 1; i < path.size(); ++i)
- cout << path[i].first << ' ' << path[i].second << endl;
- }
- int main(){
- freopen("drone.in", "r", stdin);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> w >> h;
- cin >> n;
- for (int i = 1; i <= n; ++i){
- int a, b, a1, b1;
- cin >> a >> b >> a1 >> b1;
- p[i].x = a;
- p[i].y = b;
- p[i].x1 = a1;
- p[i].y1 = b1;
- }
- for (int i = 1; i <= w; ++i){
- for (int j = 1; j <= h; ++j){
- memset(p, 0, sizeof p);
- if(ok(1, i, j)){
- print(i, j);
- return 0;
- }
- }
- }
- cout << "Impossible";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement