ProgrammingProblems/uva11101.cpp at master · rishikesha/ProgrammingProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/* Rishikesh
 * UVA  11101 Mall Mania
 */
#include<iostream>
#include<string>
#include<sstream>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<numeric>
#include<cmath>
#include<queue>

using namespace std;

struct Point {
    int x,y;
    Point(int x_, int y_) : x(x_), y(y_){}
};

void neighbors(Point p, vector<Point>& answer) {
    answer.clear();
    int x = p.x, y = p.y;

    if (x > 0)
        answer.emplace_back(x-1, y);
    if (y > 0)
        answer.emplace_back(x, y-1);
    if (x < 2000)
        answer.emplace_back(x+1, y);
    if (y < 2000)
        answer.emplace_back(x, y+1);
}

int main() {
#ifdef DEBUGUVA
    freopen("test", "r", stdin);
    cout << "This is a DEBUG\n";
#endif
    int p1, p2, x, y;
    while(cin >> p1, p1 > 0) {
        vector<vector<int>> grid1(2001, vector<int>(2001, -1)),
                        grid2(2001, vector<int>(2001, -1));
        queue<Point> q1, q2;

        for(int i = 0; i < p1; i++) {
            cin >> x >> y;
            grid1[x][y] = 0;
            q1.emplace(x,y);
        }

        cin >> p2;
        for(int i = 0; i < p2; i++) {
            cin >> x >> y;
            grid2[x][y] = 0;
            q2.emplace(x,y);
        }

        vector<Point> nbrs;

        bool done = false;
        int answer = 0;
        while(not done) {
            Point pt1 = q1.front();
            q1.pop();
            neighbors(pt1, nbrs);
            for(auto pt : nbrs) {
                if (grid2[pt.x][pt.y] >= 0) {
                    done = true;
                    answer = grid2[pt.x][pt.y] + grid1[pt1.x][pt1.y] + 1;
                    break;
                }
                if (grid1[pt.x][pt.y] < 0) {
                    grid1[pt.x][pt.y] = grid1[pt1.x][pt1.y] + 1;
                    q1.emplace(pt.x, pt.y);
                }
            }

            if (done)
                break;

            Point pt2 = q2.front();
            q2.pop();
            neighbors(pt2, nbrs);
            for(auto pt : nbrs ) {
                if (grid1[pt.x][pt.y] >= 0) {
                    done = true;
                    answer = grid1[pt.x][pt.y] + grid2[pt2.x][pt2.y] + 1;
                    break;
                }
                if (grid2[pt.x][pt.y] < 0) {
                    grid2[pt.x][pt.y] = grid2[pt2.x][pt2.y] + 1;
                    q2.emplace(pt.x, pt.y);
                }
            }
        }

        cout << answer << endl;

    }


}