解題區/解題區 - UVa

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
*/