解題區/解題區 - UVa

UVa 10266 - Surveying

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

從隨機幾點進行觀察，可以知道其相對高度。

現在給定數組觀察的部分紀錄，求在某一點的觀察的數據，如果可以得到完整的則輸出整個地圖的相對高度，如果不齊全、或者發生矛盾，則參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
1 2
1 1 10 1 2 10
1 2 20 2 2 30 2 1 30
2 2
1 1
1 1 10 1 2 10
2 2
1 2
1 1 10 1 2 10
1 1 20 1 2 30

Sample Output

1
2
3
4
5
6
0 0
10 10
the lack of measurements
conflicting measurements

Solution

不斷地部分記錄進行更新。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAXN 128
vector<int> g[MAXN][MAXN];
struct Survey {
    int x, y, h;
    Survey(int a = 0, int b = 0, int c = 0):
    x(a), y(b), h(c) {}
};
vector< vector<Survey> > D;
int n, m;
int spfa(int sx, int sy) {
    int ret[MAXN][MAXN], used[MAXN][MAXN] = {};
    vector<int> sid;
    sid.resize(D.size(), 0);
    int x, y, h, id, tx, ty;
    queue<int> X, Y, ID;
    used[sx][sy] = 1, ret[sx][sy] = 0;
    for (int i = 0; i < g[sx][sy].size(); i++) {
        int u = g[sx][sy][i];
        X.push(sx), Y.push(sy), ID.push(u);
        sid[u] = 1;
    }
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        id = ID.front(), ID.pop();
        int shift = 0;
        for (int i = 0; i < D[id].size(); i++) {
            if (D[id][i].x == x && D[id][i].y == y) {
                shift = ret[x][y] - D[id][i].h;
                break;
            }
        }
        for (int i = 0; i < D[id].size(); i++) {
            tx = D[id][i].x, ty = D[id][i].y;
            h = D[id][i].h + shift;
            if (used[tx][ty] && h != ret[tx][ty])
                return 0;
            ret[tx][ty] = h;
            if (used[tx][ty] == 0) {
                used[tx][ty] = 1;
                for (int j = 0; j < g[tx][ty].size(); j++) {
                    int u = g[tx][ty][j];
                    if (sid[u]) continue;
                    X.push(tx), Y.push(ty), ID.push(u);
                    sid[u] = 1;
                }
            }
        }
    }
    
    int ok = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ok &= used[i][j];
        }
    }
    if (ok) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%d%c", ret[i][j], j == m ? '\n' : ' ');
            }
        }
    } else {
        puts("the lack of measurements");
    }
    return 1;
}
char line[1048576 * 8];
int main() {
    int testcase, bx, by;
    int x, y, h;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        scanf("%d %d", &bx, &by);
        while (getchar() != '\n');
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                g[i][j].clear();
        D.clear();
        while (gets(line)) {
            if (line[0] == '\0')   break;
            stringstream sin(line);
            int id = (int) D.size();
            vector<Survey> item;
            while (sin >> x >> y >> h) {
                item.push_back(Survey(x, y, h));
                g[x][y].push_back(id);
            }
            D.push_back(item);
        }
        int f = spfa(bx, by);
        if (!f) {
            puts("conflicting measurements");
        }
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 3
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 2 2 30 2 1 30
 
 2 2
 1 1
 1 1 10 1 2 10
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 1 2 30
 */