解題區/解題區 - Zerojudge

b441. 延展尺寸

contents

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

Problem

將 N 張小正方形拼成長條圖，並且每一次挑選一個正方形區域黏貼在長條後，黏貼的條件是比較重疊一半的區域，利用能量最少路徑進行裁剪後併在一起。

如果最少能量大於等於某個值，則再隨機挑選一個正方形區域進行黏貼，捨棄掉這次黏貼操作，若嘗試 50 次沒有成功低於閥值，則取消全部的黏貼操作。

當初的問題在於 連續 50 次 看得似懂非懂，然後還以為是要碎形圖，只找一個正方形去重疊得到 N 個。

Sample Input

1
2
3
4
2 1
2 2
1 2 3 4 5 6
7 8 9 10 11 12

Sample Output

1
2
3
2 2
1 2 3 4 5 6
7 8 9 10 11 12

Solution

接續上一題 b438. 裁剪尺寸 的作法，現在多一個串接和重疊的操作。

感謝蔡星 asas 對此題描述的解說。

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
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h> 
using namespace std;
class IMAGE {
public:
    struct Pixel {
        int r, g, b;
        Pixel(int x = 0, int y = 0, int z = 0):
            r(x), g(y), b(z) {}
        void read() {
            scanf("%d %d %d", &r, &g, &b);
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b);
    	}
    	Pixel operator*(const double x) const {
        	return Pixel(r*x, g*x, b*x);
    	}
        Pixel operator/(const double x) const {
        	return Pixel(r/x, g/x, b/x);
    	}
    	void print() {
    		printf("%d %d %d", r, g, b);
    	}
    	int length() {
    		return abs(r) + abs(g) + abs(b);
    	}
    	double dist(Pixel x) {
    		return sqrt((r-x.r)*(r-x.r)+(g-x.g)*(g-x.g)+(b-x.b)*(b-x.b));
    	}
    };
    int W, H;
    static const int MAXN = 256;
    Pixel data[MAXN][MAXN*3], tmp[MAXN][MAXN*3];
    int energy[MAXN][MAXN], dp[MAXN][MAXN];
    long long seed;
    int random() {
    	return seed = ( seed * 9301 + 49297 ) % 233280;
    }
    void getSquarePosition(int &x, int &y, int L) {
 		y = (W <= L) ? 0 : random() % (W - L);
    	x = (H <= L) ? 0 : random() % (H - L); 
    } 
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
        seed = 0;
    }
    int isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < H && y < W;
    }
    void pattern(int L, int N) {
        int ERROR_TRY = 50;
        int threshold = round(L*255/8.0);
        int overlap = round(L/2.0);
        int lx, ly, tW = 0, path[MAXN] = {};
        for (int n = 0, it; n < N; n++) {
            for (it = 0; it < ERROR_TRY; it++) {
                getSquarePosition(lx, ly, L);
                if (n == 0) {
                    for (int i = 0; i < L; i++)
                        for (int j = 0; j < L; j++)
                            tmp[i][j] = data[lx+i][ly+j];
                    tW = L;
                    break;
                }
                for (int i = 0; i < L; i++) {
                    for (int j = 0; j < overlap; j++) {
                        energy[i][j] = round(data[lx+i][ly+j].dist(tmp[i][tW-overlap+j]));
                    }
                }
                int cost = shrink(path, L, overlap);
                if (cost < threshold) {
                    for (int i = 0; i < L; i++) {
                        for (int j = L-1; j >= path[i]; j--)
                            tmp[i][tW-overlap+j] = data[lx+i][ly+j];
                    }
                    tW += L - overlap;
                    break;
                }
            }
            if (it == ERROR_TRY)
                return ;
        }
        W = tW, H = L;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j] = tmp[i][j];
    }
    int shrink(int path[], int H, int W) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                int &val = dp[i][j];
                if (i == 0)	val = energy[i][j];
                else {	
                    val = dp[i-1][j];
                    if (j-1 >= 0)
                        val = min(val, dp[i-1][j-1]);
                    if (j+1 < W)
                        val = min(val, dp[i-1][j+1]);
                    val += energy[i][j];
                }
            }
        }
        int st = 0, cost;
        for (int i = 0; i < W; i++)
            if (dp[H-1][i] < dp[H-1][st])
                st = i;
        cost = dp[H-1][st];
        for (int i = H-1; i >= 0; i--) {
            path[i] = st;
            if (i == 0)	continue;
            int val = dp[i][st] - energy[i][st];
            if (st-1 >= 0 && val == dp[i-1][st-1])
                st = st-1;
            else if (val == dp[i-1][st])
                st = st;
            else
                st = st+1;
        }
        return cost;
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    int n, L, N;
    scanf("%d %d", &L, &N);
    test.read();
    test.pattern(L, N);
    test.print();
    return 0;
}