UVa 12871 - Landmine Cleaner

contents

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

Problem

給予每一個格子的得分,分數為鄰近九格的 L 個數 (1 個 1 分) 加上自己是否為 L (3 分),因此最低 0 分,最高 12 分。

保證只有唯一解。

Sample Input

1
2
3
4
5
1
3 4
2 6 3 2
7 5 7 5
6 7 3 2

Sample Output

1
2
3
-L--
L-LL
LL--

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 1024

int A[MAXN][MAXN], solv[MAXN][MAXN];
int g[MAXN][MAXN];
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
int n, m;
int isplace(int x, int y) {
int v = A[x][y], tx, ty;
int unknown = 0, score = 0;
for (int i = 0; i < 8; i++) {
tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (solv[tx][ty]) score += g[tx][ty];
else unknown++;
}
if (v < 3) return -1;
if (v > 8) return 1;
if (score + unknown < v) return 1;
if (score + 4 > v) return -1;
return 0; // not sure.
}
int main() {
int testcase;
int t;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &A[i][j]);
}
}
memset(solv, 0, sizeof(solv));
int test = n * m;
while (test) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (solv[i][j]) continue;
int t = isplace(i, j);
if (t) {
test--;
g[i][j] = t > 0;
solv[i][j] = 1;
}
}
}

}
for (int i = 0; i < n; i++, puts("")) {
for (int j = 0; j < m; j++) {
if (solv[i][j])
putchar(g[i][j] ? 'L' : '-');
else {
assert(false);
}
}
}
}
return 0;
}
/*
9999
3 4
2 6 3 2
7 5 7 5
6 7 3 2

3 3
7 9 7
9 12 9
7 9 7

3 1
0
0
0

*/