解題區/解題區 - UVa

UVa 12872 - Hidden Plus Signs

contents

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

Problem

盤面上放置許多 + 展開，保證寬高相同並且不會超出格子外部，同時每一個大小不超過 11。而十字中心不會被其他十字覆蓋，每一格會顯示被覆蓋幾次。

找到一種放置方法，復原盤面結果，如果有種放置方法，選擇一種字典順序最小的輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0

Sample Output

1
2
3
4
2
3 3
9
8 10

Solution

論窮舉順序的重要性，將會導致速度的快慢。

原則上先把所有 1 的位置挑出，依序窮舉每一個 1 是否可以進行放置。每一次選擇放置時，先從最大的寬高開始嘗試，先塞掉大多數的盤面結果，否則速度會被拉下。

不確定這一題是否有很正統的作法，求指導。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int g[32][32], n, m;
int A[900][2], N, SUM = 0;
int isEmpty() {
    return SUM == 0;
}
void remove(int x, int y, int w) {
    for (int i = x - w; i <= x + w; i++)
        g[i][y]--, SUM--;
    for (int i = y - w; i <= y + w; i++)
        g[x][i]--, SUM--;
    g[x][y]++, SUM++;
}
void resume(int x, int y, int w) {
    for (int i = x - w; i <= x + w; i++)
        g[i][y]++, SUM++;
    for (int i = y - w; i <= y + w; i++)
        g[x][i]++, SUM++;
    g[x][y]--, SUM--;
}
int place(int x, int y, int w) {
    for (int i = x - w; i <= x + w; i++)
        if (!g[i][y])
            return 0;
    for (int i = y - w; i <= y + w; i++)
        if (!g[x][i])
            return 0;
    return 1;
}
int dfs(int idx, int used, int LX, int LY) {
    if (isEmpty()) {
        printf("%d\n%d %d\n", used, LX + 1, LY + 1);
        return 1;
    }
    if (idx == N)
        return 0;
    int t = min(min(A[idx][0], A[idx][1]), min(n - 1 - A[idx][0], m - 1 - A[idx][1]));
    for (int i = t; i >= 1; i--) {
        if (place(A[idx][0], A[idx][1], i)) {
            remove(A[idx][0], A[idx][1], i);
            if (dfs(idx+1, used + 1, A[idx][0], A[idx][1]))
                return 1;
            resume(A[idx][0], A[idx][1], i);
        }
    }
    if (dfs(idx+1, used, LX, LY))
        return 1;
    return 0;
}
int main() {
    int testcase;
    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", &g[i][j]), SUM += g[i][j];
        N = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 1)
                    A[N][0] = i, A[N][1] = j, N++;
        dfs(0, 0, -1, -1);
    }
    return 0;
}
/*
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0
*/