解題區/解題區 - UVa

UVa 1045 - The Great Wall Game

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
5                                                                
1 2 2 4 3 4 5 1 5 3                                             
2                                                                
1 1 1 2                                                         
3                                                                
3 1 1 2 2 2                                                       
0

Sample Output

1
2
3
4
5
Board 1: 6 moves required.
  
Board 2: 0 moves required.
  
Board 3: 1 moves required.

Solution

窮舉要移動到哪裡，然後找完美匹配的最大權重 - KM 算法。

只要將移動步數弄成負權重套上去 KM 即可。

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
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct KM {
    int W[105][105], N;
    int mx[105], my[105]; // match arr
    int lx[105], ly[105]; // label arr
    int x[105], y[105]; // used arr
    int hungary(int nd) {
        int i;
        x[nd] = 1;
        for(i = 0; i < N; i++) {
            if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
                y[i] = 1;
                if(my[i] == -1 || hungary(my[i])) {
                    my[i] = nd;
                    return 1;
                }
            }
        }
        return 0;
    }
    int run() {
        int i, j, k, d;
        memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
        for (int i = 0; i < N; i++)
        	lx[i] = -0x3f3f3f3f, ly[i] = 0;
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
        for(i = 0; i < N; i++) {
            while(1) {
                memset(x, 0, sizeof(x));
                memset(y, 0, sizeof(y));
                if(hungary(i))  break;
                d = 0x3f3f3f3f;
                for(j = 0; j < N; j++) {
                    if(x[j]) {
                        for(k = 0; k < N; k++)
                            if(!y[k])
                            d = d < lx[j]+ly[k]-W[j][k] ?
                                d : lx[j]+ly[k]-W[j][k];
                    }
                }
                if(d == 0x3f3f3f3f)  break;
                for(j = 0; j < N; j++) {
                    if(x[j])    lx[j] -= d;
                    if(y[j])    ly[j] += d;
                }
            }
        }
        int res = 0;
        for(i = 0; i < N; i++) {
            if(my[i] != -1)
                res += W[my[i]][i];
        }
        return res;
    }
} km;
int dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
    int cases = 0;
    int n, x[105], y[105];
    while(scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
        	scanf("%d %d", &x[i], &y[i]);
        	x[i]--, y[i]--;
        }
        km.N = n;
        int ret = -0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		for (int k = 0; k < n; k++)
        			km.W[j][k] = -dist(x[j], y[j], i, k);
        	ret = max(ret, km.run());
        }
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		for (int k = 0; k < n; k++)
        			km.W[j][k] = -dist(x[j], y[j], k, i);
        	ret = max(ret, km.run());
    	}
    	for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		km.W[j][i] = -dist(x[j], y[j], i, i);	
    	}
        ret = max(ret, km.run());
    	for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		km.W[j][i] = -dist(x[j], y[j], i, n - i - 1);
    	}
        ret = max(ret, km.run());
        printf("Board %d: %d moves required.\n\n", ++cases, -ret);
    }
    return 0;
}