學校課程/資料庫系統

資料庫複習 Ch.13

Chapter 13

Design Theory for Relational Databases

名詞定義

  • Functional Dependencies

    • 定義
      X -> Y is an assertion about a relation R that whenever two tuples of R agree on all the attributes of X , then they must also agree on all attributes in set Y .
    • 特性
      • X->A1A2 … An holds for R exactly when each of X->A1, X->A2,…, X->An hold for R.
        例子 Drinkers(name, addr, beersLiked, manf, favBeer)
        FD : name -> addr favBeer & beersLiked -> manf
        name -> addr favBeer = name -> addr and name -> favBeer .

  • Keys of Relations
    換句話說 superkey 可能是複合的好幾個 key 構成，因此 key 一定也是 superkey，不論 superkey 或者是 key 都可以決定所有的 attribute。特別注意，key 是最小單位，因此 key 的子集不會是 key。

    • superkey
      K is a superkey for relation R if K functionally determines all of R.
    • key
      K is a key for R if K is a superkey, but no proper subset of K is a superkey.
    • 例子 Drinkers(name, addr, beersLiked, manf, favBeer)
      FD : name -> addr favBeer & beersLiked -> manf
      得到 {name, beersLiked} 是一個 superkey，發現 {name} 和 {beersLiked} 不是 superkey，得到 {name, beersLiked} 是一個 key。

  • Inference Test
    如何找到 inferring FD？所謂的 inferring FD 就是藉由遞移關係得到的 FD，可以由原本集合中的幾個 FD 推斷出來，因此這些 inferring FD 不是必要存在的。那就先把 Y -> B 移除，再由剩下的 FD 組合，查看是否存在可以推論出 B 的可能，如果任何情況都推不出 B，則 Y -> B 不是 inferring FD。
    We are given FD’s X1 -> A1, X2 -> A2,…, Xn -> An , and we want to know whether an FD Y -> B must hold in any relation that satisfies the given FD’s.
    例子 If A -> B and B -> C hold, surely A -> C.

  • Closure Test
    遞移閉包測試。
    An easier way to test is to compute the closure of Y , denoted Y+ .

    • Basis: Y+ = Y.
    • Induction: Look for an FD’s left side X that is a subset of the current Y+ . If the FD is X -> A, add A to Y+ .

Relational Schema Design

schema design 目標是避免異常、冗餘。

Goal of relational schema design is to avoid anomalies and redundancy.

  • Update anomaly :
    更新異常，當一個事實改變時，只會發生一次修改，而不會發生很多次的修改。意即針對一個關聯屬性修改，最多更動一個 row (entity)，不會更動數行的 row。
    one occurrence of a fact is changed, but not all occurrences.

  • Deletion anomaly :
    刪除異常，當一個 row 移除時，確定合法的事實被移除。如果發生關聯上屬性移除，但該屬性本應該存在，卻遭到移除而不存在資料庫中，就這麼地憑空消失。
    valid fact is lost when a tuple is deleted.

  • Boyce-Codd Normal Form
    無論怎麼找 FD，都會發現到 FD 的 left hand side X 都是 superkey，那麼 R 就是一個 BCNF 。
    We say a relation R is in BCNF if whenever X ->Y is a nontrivial FD that holds in R, X is a superkey.

    • nontrivial means Y is not contained in X.
    • a superkey is any superset of a key (not necessarily a proper superset).
    • 例子 Drinkers(name, addr, beersLiked, manf, favBeer)
      FD : name -> addr favBeer & beersLiked -> manf
      In each FD, the left side is not a superkey. Shows Drinkers is not in BCNF.

  • Decomposition into BCNF 

1
2
3
4
5
6
7
BCNF_Decompose(R, FD)
    find X s.t.: X != (X+) != [all attributes] // X is one of FD's left hand side
    if (not found) then “R is in BCNF”
    let Y = (X+) - X
    let Z = [all attributes] - (X+)
    decompose R into R1(X union Y) and R2(X union Z) 
    continue to decompose recursively R1 and R2

Third Normal Form

接續上面的 Decomposition，將會產生一些問題。拆分上不合乎常理，發生過度的拆分，這問題發生在於給定的 FD 格式。

舉個例子 (street address, city, zip code)

  • FD : AB -> C and C -> B.
    Example: A = street address, B = city, C = zip code.
  • There are two keys, {A, B} and {A, C} .
  • C -> B is a BCNF violation, so we must decompose into AC, BC.
  • 顯然地 AC 有很嚴重的問題，既不存在 A -> C 也不存在 C -> A。

避免此問題

  • An attribute is prime if it is a member of any key. 也就是 attribute 是某一 key 的 subset。
  • X -> A violates 3NF if and only if X is not a superkey, and also A is not prime.

接續上個例子 (street address, city, zip code)

  • There are two keys, {A, B} and {A, C} .
  • Thus A, B, and C are each prime.
  • Although C -> B violates BCNF, it does not violate 3NF.

properties of a decomposition

最後，來看看得到的 3NF 和 BCNF 給予什麼特性？

There are two important properties of a decomposition:

  • Lossless Join :
    it should be possible to project the original relations onto the decomposed schema, and then reconstruct the original.
  • Dependency Preservation :
    it should be possible to check in the projected relations whether all the given FD’s are satisfied.

資料不失真，保證可以藉由投影、Join 將分解的 schema 組合成原本的資料。同時所有的相依關係仍然保留，可以把原本 FD 都滿足所有的 schema。

Read More +
學校課程/資料庫系統

資料庫複習 Ch.12

Chapter 12

E/R Model

Entity-Relationship Model 實體關係模型

The E/R model allows us to sketch database schema designs.

協助描繪資料庫 schema 設計，藉由 E/R model 映射到資料庫的 Relation model。

名詞定義

  • Entity = “thing” or object.
    實體，對應到現實生活中的名詞，例如蘋果 mac2013、微軟 win8、 … 等。單指一個、一件實體存在。
  • Entity set = collection of similar entities.
    很多類似的實體產生的集合，例如計算機、員工 … 等實體集合。
    Similar to a class in object-oriented languages.
  • Attribute = property of (the entities of) an entity set.
    屬性，通常是一個數值的呈現，例如計算機的運算能力、員工薪資、 … 等。
    Attributes are simple values, e.g. integers or character strings, not structs, sets, etc.

繪製 E/R Diagrams 時，呈現方式

  • Entity set = rectangle.
    實體集合使用矩形圖表示
  • Attribute = oval,
    屬性使用橢圓表示，並且連到實體集合，表示這些實體集合都具有這些屬性特徵。
    with a line to the rectangle representing its entity set.

  • Relationships = diamond.
    用菱形連接兩個以上的實體集合，表示實體集合之間的關係。
    A relationship connects two or more entity sets, with lines to each of the entity sets involved.

  • Relationship Set
    The “value” of a relationship is a relationship set, a set of tuples with one component for each related entity set.
    For the relationship Sells , we might have a relationship set like:

Bar Beer
Joe’s Bar Bud
Joe’s Bar Miller
Sue’s Bar Bud
Sue’s Bar Pete’s Ale
Sue’s Bar Bud Lite
  • Multiway Relationships
    Our three binary relationships Likes , Sells , and Frequents do not allow us to make this distinction.
Bar Drinker Beer
Joe’s Bar Ann Miller
Sue’s Bar Ann Bud
Sue’s Bar Ann Pete’s Ale
Joe’s Bar Bob Bud
Joe’s Bar Bob Miller
Joe’s Bar Cal Miller
Sue’s Bar Cal Bud Lite

  • Rounded arrow = “exactly one,”
    實心箭頭表示確切對應一個關係，如果一個人會喜愛好幾種酒，其中最愛某一種。
    i.e., each entity of the first set is related to exactly one entity of the target set.

  • Roles
    Label the edges between the relationship and the entity set with names called roles.
    例如丈夫、妻子之間的關係、夥伴之間的關係。

Husband Wife
Bob Ann
Joe Sue
Buddy1 Buddy2
Bob Ann
Joe Sue

  • Subclass = special case = fewer entities = more properties.
    從物件導向來說，一個繼承關係，得到的 Subclass 會繼承原本的 Class 的特徵、關係，有可能會具有額外的特徵。
    Let us suppose that in addition to all the properties (attributes and relationships) of beers, ales also have the attribute color . Isa triangles ( is a 的三角形) indicate the subclass relationship. Point to the superclass (指向父類別).

    • 比較 OO 和 E/R 對 subclass 的定義
      也就是說，OO 只會用 is a 描述一個 subclass 的繼承關係。但在 E/R model 中，isa 相當一個欄位，用來描述它是哪一個子類別，也就是說在紀錄時，如果它在某一個子類別時，那麼在父類別中也會記錄到它。
      • In OO, objects are in one class only. Subclasses inherit from superclasses.
      • In contrast, E/R entities have representatives in all subclasses to which they belong.
        • Rule : if entity e is represented in a subclass, then e is represented in the superclass (and recursively up the tree).

  • Key
    Key 是一個 attribute 的集合構成，得到 f(Key) = at most one entity 。繪製時，使用底線 (underline) 於作為 key attribute 表示。
    is a set of attributes for one entity set such that no two entities in this set agree on all the attributes of the key.

  • Weak Entity Sets
    為了去辨識某個實體，必須倚靠一對一、或者多對一的關係，來確切地找到某個實體。
    Entity set E is said to be weak if in order to identify entities of E uniquely, we need to follow one or more many-one relationships from E and include the key of the related entities from the connected entity sets.

    • 例如 Player(name, nubmer) - Plays_on -> Team(name)。當知道 Team 是哪一個時，才能辨識出 Player，否則名稱跟號碼可能會在不同隊中出現重複的。因此 Player 就是一個 Weak Entity Sets 。

  • Weak Entity-Set Rules
    A weak entity set has one or more many-one relationships to other (supporting) entity sets.
    並不是每一個 relationship 都是 weak entity set 需要的支持。然而被需要的 relationship 必然擁有一個 rounded arrow 。
    The key for a weak entity set is its own underlined attributes and the keys for the supporting entity sets.
    例如在之前的例子，可以使用 (player) number 和 (team) name 作為 Player 的 key。

Design Techniques

  • Design Techniques
    • Avoid redundancy.
      避免冗餘
    • Limit the use of weak entity sets.
      限制 weak entity set 的使用
    • Don’t use an entity set when an attribute will do.
      如果能使用一個 attribute 表示，則無需增加一個 entity set 單獨表示一個 attribute。

分別對應以下幾點。

  • Redundancy = saying the same thing in two (or more) different ways
    存在用好幾種方法說一件事情，或者提及某個屬性。

  • Entity Sets Versus Attributes
    對應實體集合的屬性，要符合以下兩點，屬性應為很多實體共同擁有的名稱，並且擁有至少一個 nokey 屬性，或者屬於 many-one 或 many-many 關係中，many 那一方的 entity set。
    An entity set should satisfy at least one of the following conditions:

    • It is more than the name of something; it has at least one nonkey attribute. or
    • It is the “many” in a many-one or many-many relationship

  • Weak Entity Sets 使用須知

    • 避免濫用，通常能夠創建一個 unique ID 來表示一個實體。
    • 當真的找不到一個普遍性的 unique ID 時，才會逼不得已使用 Weak entity set.

From E/R Diagrams to Relations

關於對應的名詞如下，轉換時找 attribute 時，E/R Diagrams 中的 relationships 也會成為一個 relation ，attribute 的找法，可以從關聯的 entity set 的 key 或者是關係的定義本身。

  • Entity set -> relation.
  • Attributes -> attributes.

  • Relationships -> relations whose attributes are only:

    • The keys of the connected entity sets.
      將相連的實體集合的 key 值都拿來作為 attribute。
    • Attributes of the relationship itself.

  • Combining Relations
    結合 Relation，減少 Relation 的個數，將多對一的 relationships 表單，而實體集合屬於 many 的那一方，則可以把 one 那一方結合在一起。切記一定要是多對一，如果是多對多則會造成冗餘發生。

    • The relation for an entity-set E
    • The relations for many-one relationships of which E is the “many.”
    • Example: Drinkers(name, addr) and Favorite(drinker, beer) combine to make Drinker1(name, addr, favBeer).

  • Handling Weak Entity Sets
    解決 weak entity set 轉化成 relation 時，必然要為它準備一個 complete key 來辨識不同實體於關連到不同的實體集合。如果一個 supporting relationship 不具有 attribute，而且屬於一個冗餘的紀錄，那麼把 relationship 另一方 “one” 的 entity set 的 key 值加入到 weak entity set 所創建的 relation。
    從之前的例子，把球隊名稱 team(name) 加入到 Player(number, name) 中，變成 relation Player(number, team_name, name)，這是在之前的 Combining Relations 中，就已經得到的結果，因此就可以忽略。

    • Relation for a weak entity set must include attributes for its complete key (including those belonging to other entity sets), as well as its own, nonkey attributes.
    • A supporting relationship is redundant and yields no relation (unless it has attributes).

  • Subclasses: Three Approaches

    • Object-oriented : One relation per subset of subclasses, with all relevant attributes.
      父類別和子類別分開，各自成為一個 relation。
    • Use nulls : One relation; entities have NULL in attributes that don’t belong to them.
      把子類別的屬性上提，如果父類別不存在該屬性則填入 null。
    • E/R style : One relation for each subclass:
      存在父類別和子類別的 relation，但是共同屬性都會在父類別中，子類別只保留 key 和新增加的屬性。
      • Key attribute(s).
      • Attributes of that subclass.
Read More +
解題區/解題區 - UVa

UVa 11186 - Circum Triangle

Problem

半徑為 R 的圓上有 N 個點，請問任挑三點形成的三角形面積總和為多少。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 10
10.00
100.00
300.00
310.00
320.00
3 20
10.00
100.00
300.00
0 0

Sample Output

1
2
286
320

Solution

因此總共有 C(N, 3) 的三角形，聽說直接窮舉三點計算三角形面積就可以過，時間複雜度是 O(n^3)。事實上可以換個方式想，計算三角形面積，相當於用一個圓減去三個弓形面積。

那麼實際上會有 C(N, 3) 個圓減去一堆弓形面積。關於所有弓形面積的計算，可以窮舉兩點拉一條邊作為弦，接著會有兩個弓形，分別找到左右兩側的點數，就能知道有多少三角形分別使用多少次這些弓形面積，加總之後就是總共的弓形面積，複雜度降至 O(n^2)。

事實上還可以再更數學點，但是不太會推導，最後貌似可以在 O(n) 完成。

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
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const double pi = acos(-1);
int main() {
    int N;
    double R, theta[512];
    while (scanf("%d %lf", &N, &R) == 2 && N) {
        for (int i = 0; i < N; i++) {
            scanf("%lf", &theta[i]);
            theta[i] = theta[i] * pi / 180;
        }
        sort(theta, theta+N);
        double ret = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int a = j - i - 1;
                int b = N - a - 2;
                double A, B, t = theta[j] - theta[i];
                A = t /2 * R * R - R * R * sin(t)/2;
                B = R * R * pi - A;
                ret += a * B + b * A;
//				printf("[%lf %lf] %lf %lf\n", theta[i], theta[j], A, B);
            }
        }
        ret = (double)(N) * (N-1) * (N-2) / 6 * R * R * pi - ret;
        if (N < 3)	ret = 0;
        printf("%.0lf\n", ret);
    }
    return 0;
}
/*
5 10
10.00
100.00
300.00
310.00
320.00
3 20
10.00
100.00
300.00
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 904 - Overlapping Air Traffic Control Zones

Problem

每一個飛機的安全範圍視為在三維空間平行三軸的六面體，給定 n 台飛機的安全範圍，請問重疊至少兩次的空間體積為何？

Sample Input

1
2
3
4
5
6
5
1 1 1 3 3 3
1 1 1 3 3 3
1 1 1 3 3 3
400000000 400000000 400000000 400000001 400000001 400000002
400000000 400000000 400000000 400000002 400000004 400000001

Sample Output

1
9

Solution

離散化 X Y Z 軸出現的座標值，壓縮成 n * n * n 的三維陣列，接著將每一台飛機的安全範圍離散化後，將其所在的位置進行標記。

離散化後，每一格將會具有不同的長度，把離散的數據聚集在一起，而事實上在工程數學中，離散化一詞則是將連續的數據變成整數離散的情況。

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
#include <stdio.h>
#include <map>
using namespace std;
#define MAXN 32
void mapRelabel(map<int, int> &R, int val[]) {
    int size = 0;
    for (map<int, int>::iterator it = R.begin();
        it != R.end(); it++) {
        val[size] = it->first;
        it->second = size++;
    }
}
int main() {
    int n;
    int lx[MAXN], ly[MAXN], lz[MAXN];
    int rx[MAXN], ry[MAXN], rz[MAXN];
    int xval[MAXN], yval[MAXN], zval[MAXN];
    while (scanf("%d", &n) == 1) {
        map<int, int> RX, RY, RZ;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &lx[i], &ly[i], &lz[i]);
            scanf("%d %d %d", &rx[i], &ry[i], &rz[i]);
            RX[lx[i]] = RX[rx[i]] = 1;
            RY[ly[i]] = RY[ry[i]] = 1;
            RZ[lz[i]] = RZ[rz[i]] = 1;
        } 
        mapRelabel(RX, xval);
        mapRelabel(RY, yval);
        mapRelabel(RZ, zval);
        
        int a = RX.size(), b = RY.size(), c = RZ.size();
        int sx, ex, sy, ey, sz, ez;
        int cnt[MAXN][MAXN][MAXN] = {};
        for (int i = 0; i < n; i++) {
            sx = RX[lx[i]], ex = RX[rx[i]];
            sy = RY[ly[i]], ey = RY[ry[i]];
            sz = RZ[lz[i]], ez = RZ[rz[i]];
            for (int p = sx; p < ex; p++) {
                for (int q = sy; q < ey; q++) {
                    for (int r = sz; r < ez; r++) {
                        cnt[p][q][r]++;
                    }
                }
            }
        }
        
        int ret = 0;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                for (int k = 0; k < c; k++) {
                    if (cnt[i][j][k] >= 2) {
                        ret += (xval[i+1] - xval[i]) * (yval[j+1] - yval[j]) * (zval[k+1] - zval[k]);
                    }
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10729 - Treequivalence

Problem

給一個平面圖的樹，請問是否同構，每一個節點相鄰的邊將會按照逆時針的順序給定。

Sample Input

1
2
3
4
5
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

Sample Output

1
2
different
same

Solution

這一題與 UVa 12489 - Combating cancer 有點不同，這一題限制在平面圖，因此邊的紀錄是有順序性的。而題目不僅要求結構相同，同時在節點上面的 label 也要相同。

但是只要固定一個當作根，成為一個有根樹，那麼在最小表示法中，除了根的分支可以旋轉外，其餘的節點的分支都不能旋轉。因此固定其中一棵樹的根節點，接著窮舉另外一棵樹哪個節點作為根節點，分別找到最小表示法進行比對即可。

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
143
144
145
146
147
148
149
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
// special !!!!!!!! normal planar representation
class Tree {
    public:
    vector<int> g[10005];
    char label[10005];
    int n;
    map<vector<int>, int> tmpR;
    int dfsMinExp(int u, int p) {
        vector<int>	branch;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(v == p)	continue;
            branch.push_back(dfsMinExp(v, u));
        }
        sort(branch.begin(), branch.end());
    
        int a = 63689, b = 378551;
        int ret = 0;
        branch.push_back(label[u]);
        for(int i = 0; i < branch.size(); i++)
            ret = ret * a + branch[i], a *= b;
        return ret;
    }
    vector<int> getTreeMinExp() { // simple (no plane)
        if(n == 1)	return vector<int>(1, (int)label[1]);
        int deg[10005] = {}, u, v;
        int topo[10005] = {}, idx = 0;
        queue<int> Q;
        for(int i = 1; i <= n; i++) {
            deg[i] = g[i].size();
            if(deg[i] == 1)	Q.push(i);
        }
        while(!Q.empty()) {
            u = Q.front(), Q.pop();
            topo[idx++] = u;
            for(int i = 0; i < g[u].size(); i++) {
                v = g[u][i];
                if(--deg[v] == 1)
                    Q.push(v);
            }
        }
        vector<int> ret;
        ret.push_back(dfsMinExp(topo[idx-1], -1));
        ret.push_back(dfsMinExp(topo[idx-2], -1));
        return ret;
    }
    
    int dfsCheck(Tree& tree, int u, int p) {
        vector<int> branch;
        if (p < 0) { // root
            for (int i = 0; i < tree.g[u].size(); i++) {
                int v = tree.g[u][i];
                branch.push_back(dfsCheck(tree, v, u));
            }
            
            int idx = 0, bn = branch.size();
            for (int s = 1; s < bn; s++) { // find cycle minExp
                for (int i = idx, j = s, k = 0; k < bn; k++) {
                    if (branch[i] != branch[j]) {
                        if (branch[j] < branch[i])	idx = s;
                        break;
                    }
                    if (++i >= bn)	i = 0;
                    if (++j >= bn)	j = 0;
                }
            }
            rotate(branch.begin(), branch.begin() + idx, branch.end());
        } else {
            int idx;
            for (idx = 0; tree.g[u][idx] != p; idx++);
            
            while (true) {
                idx++;
                if (idx >= tree.g[u].size())
                    idx = 0;
                int v = tree.g[u][idx];
                if (v == p)	break;
                branch.push_back(dfsCheck(tree, v, u));
            }
        }
        branch.push_back(-tree.label[u]);
        int &ret = tmpR[branch];
        if (ret == 0)	ret = tmpR.size();
        return ret;
    }
    int equal(Tree &other) { // normal planar representation
        if (n != other.n)	return 0;
        tmpR.clear();
        int b = dfsCheck(other, 1, -1);
        for (int i = 1; i <= n; i++) {
            int a = dfsCheck(*this, i, -1);
            if (a == b)
                return 1;
        }
        return 0;
    }
    void init(int N) { 
        for (int i = 0; i <= N; i++)
            g[i].clear();
        n = 0;
    } 
    int read(int p) {
        int x = ++n;
        char c;
        if (p >= 0)	g[x].push_back(p);
        scanf(" %c%c", &label[x], &c);
        if (c != '(') {
            ungetc(c, stdin);
            return x;
        }
        do {
            g[x].push_back(read(x));
            if (scanf("%c", &c) != 1 || c != ',')
                break;
        } while (true);
        return x;
    }
} tree1, tree2;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        tree1.init(256); tree2.init(256);
        tree1.read(-1); tree2.read(-1);
        int same = tree1.equal(tree2);
        puts(same ? "same" : "different");
    }
    return 0;
}
/*
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))
9999
S(Y(Y(O),U(N(S,E,R(D)))))
D(R(N(U(Y(Y(O),S)),S,E)))
*/
Read More +
解題區/解題區 - UVa

UVa 10335 - Ray Inside a Polygon

Problem

給一個凸多邊形，接著再給定一射線的起始位置和角度，請問經過 m 次反射後的位置為何？如果射線打入凸多邊形的端點時，視如射線遺失。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
0 0

Sample Output

1
2
lost forever...
4.00 2.00

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
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
// I hate it, more eps adjust. 
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
int same(Pt a, Pt b) {
    return fabs(a.x - b.x) < 0.005 && fabs(a.y - b.y) < 0.005;
}
int main() {
    Pt p[32];
    double theta;
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        Pt S, lvec;
        S.read();
        scanf("%lf", &theta);
        theta = theta * pi / 180;
        lvec = Pt(cos(theta), sin(theta));
        for (int i = 0; i < n; i++) // anti-clockwise
            p[i].read();
        
        int lost = 0;
        Seg on;
        for (int i = 0, j = n-1; i < n; j = i++) {
            Seg b(p[j], p[i]);
            if (onSeg(b.s, b.e, S))
                on = b;
        }
        for (int it = 0; it <= m; it++) { // #reflect.
            Seg pick = on, a(S, S + lvec);
            for (int i = 0, j = n-1; i < n; j = i++) {
                Seg b(p[j], p[i]);
                if (cmpZero(cross(a.s, a.e, b.s)) * cmpZero(cross(a.s, a.e, b.e)) <= 0) {
                    if (b != pick) {
                        pick = b;
                        break;
                    }
                }
            }
            Pt poj = getIntersect(pick, Seg(S, S + Pt(pick.s.y - pick.e.y, pick.e.x - pick.s.x)));
            Pt sym = S + (poj - S) * 2;
            S = getIntersect(a, pick);	
            lvec = S - sym;			
//			printf("%lf %lf %lf %lf\n", pick.s.x, pick.s.y, pick.e.x, pick.e.y);
//			printf("%lf %lf\n", S.x, S.y);
            if (same(S, pick.s) || same(S, pick.e)) {
                lost = 1;
                break;
            }
//			double r;
//			if (dot(pick.e - pick.s, lvec) <= 0)
//				r = getAngle(lvec, pick.e - pick.s);
//			else
//				r = getAngle(lvec, pick.s - pick.e);
//			lvec = rotateRadian(lvec, 2 * r);
            on = pick;
//			printf("it %d: %lf %lf\n", it, S.x, S.y);
//			printf("%lf %lf %lf %lf\n", lvec.x, lvec.y, poj.x, poj.y);
        }
        if (lost)
            puts("lost forever...");
        else {
            if (fabs(S.x) < eps && S.x < 0)
                S.x = - S.x;
            if (fabs(S.y) < eps && S.y < 0)
                S.x = - S.y;
            printf("%.2lf %.2lf\n", S.x, S.y);
        }
    }
    return 0;
}
/*
4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
3 501
10.99 109 0
10 10
11 110
11 10
3 0
1 0 91
0 0
5 5
5 0
3 1
1 0 91
0 0
5 5
5 0
3 2
1 0 91
0 0
5 5
5 0
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 12684 - VivoParc

Problem

動物園的 4 種動物配置，動物都有地域性，不希望相鄰的地方會具有與自己相同的物種。

給一個 graph，最多用四個顏色著色，使得相鄰不同色，輸出任意種方案即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8

Sample Output

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

Solution

看起來 N 還算大，窮舉順序會稍微影響速度，依序窮舉節點，檢查是否存在相鄰同色。由於不曉得是不是只有一個連通元件，連通元件分開找解，防止浪費時間的搜索。

接著根據 bfs 順序進行窮舉，來加快退回的速度。事實上也發現到四色問題如果保證有解，事實上應該很容易找到其中一組解。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[128];
int visited[128];
int A[128], An, color[128];
int used[128];
int dfs(int idx) {
    if (idx == An)
        return 1;
    for (int c = (idx == 0 ? 4 : 1); c <= 4; c++) {
        int u = A[idx], v, ok = 1;
        for (int i = 0; i < g[u].size() && ok; i++) {
            v = g[u][i];
            if (used[v] && color[v] == c)
                ok = 0;
        }
        if (ok) {
            used[u] = 1;
            color[u] = c;
            if (dfs(idx+1))
                return 1;
            used[u] = 0;
        }
    }
    return 0;
}
void bfs(int st) {
    queue<int> Q;
    int u;
    An = 0;
    Q.push(st), visited[st] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        A[An++] = u;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (visited[v] == 0) {
                visited[v] = 1;
                Q.push(v);
            }
        }
    }
    memset(used, 0, sizeof(used));
    dfs(0);
}
int main() {
    char line[128];
    int x, y, n, cases = 0;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n'); 
        for (int i = 0; i <= n; i++)
            g[i].clear();
        while (gets(line)) {
            if (line[0] == '\0')
                break;
            sscanf(line, "%d-%d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) {
            sort(g[i].begin(), g[i].end());
            g[i].resize(distance(g[i].begin(), unique(g[i].begin(), g[i].end())));
        }
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                bfs(i);
            }
        }
        if (cases++)	puts("");
        for (int i = 1; i <= n; i++)
            printf("%d %d\n", i, color[i]);
    }
    return 0;
}
/*
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8
*/
Read More +
解題區/解題區 - UVa

UVA 12763 - Dicey Dice

Problem

有兩個玩家 A, B，盤面上有三個骰子，先手先挑一個骰子出來，後手再從剩餘兩個骰子中挑一個。接著兩個人會分別骰出點數，骰出最大的那個玩家獲勝，如果骰出一樣點數則平手

給予先手玩家，和三個六面骰子，請問獲勝機率高的玩家為何？

Sample Input

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

Sample Output

1
2
3
A
B
fair

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    char s[10];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int player = s[0] - 'A';
        int dice[3][6];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 6; j++) {
                scanf("%d", &dice[i][j]);
            }
        }
        double rmx = 0, rmx2 = 1;
        for (int i = 0; i < 3; i++) { // A player pick
            double mx = 1, mx2 = 0;
            for (int j = 0; j < 3; j++) { // B player pick
                if (i == j)	continue;
                int pa = 0, pb = 0;
                for (int p = 0; p < 6; p++) {
                    for (int q = 0; q < 6; q++) {
                        pa += dice[i][p] > dice[j][q];
                        pb += dice[i][p] < dice[j][q];
                    }
                }
                
                if (mx > pa / 36.0 || (mx == pa / 36.0 && mx2 < pb/36.0)) {
                    mx = pa /36.0;
                    mx2 = pb / 36.0;
                }
            }
            if (rmx < mx || (rmx == mx && rmx2 > mx2)) {
                rmx = mx;
                rmx2 = mx2;
            }
        }
        if (rmx > rmx2)
            printf("%c\n", player + 'A');
        else if (rmx < rmx2)
            printf("%c\n", 1 - player + 'A');
        else
            printf("fair\n");
//			printf("%lf %lf\n", rmx, rmx2);
    }
    return 0;
}
/*
3
A
1 1 1 1 1 1
2 3 2 4 5 3
6 6 6 6 6 6
A
4 3 7 9 2 5
8 1 4 6 9 2
6 5 1 8 3 7
B
1 2 3 4 4 4
1 2 3 4 4 4
1 2 3 4 4 4
*/
Read More +
解題區/解題區 - UVa

UVa 12769 - Kool Konstructions

Problem

有一長度為 n 的都市地帶，每一次將會做區段的都市更新，將建築物都增加高度 v。

操作

  • B X Y V ： 將區間 [X, Y] 都增加 V 高度
  • Q X ： 詢問當前位置 X 的建築物高度為何

(題目中的圖示貌似有錯誤)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
0

Sample Output

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

Solution

想要區間更新、單點查詢，有兩種方案 segment tree 附加懶操作、或者 binary indexed tree、最後是塊狀鏈表這幾種方式。這裡使用 binary indexed tree。雖然 binary indexed tree 原本的操作是單點修改，前綴總和查找。利用這一點完成區間修改的操作。

由於這一題還是單純的加法，那麼符合加法原則，當區間修改 B X Y V 時，相當於修改單點 Arr[X] += V，Arr[Y+1] -= V，從前綴和 SUM[1...Z] = \sum Arr[i]來看，保證只有區間 [X, Y] 的詢問增加了 V 值，其他保持不變。

單筆操作都是 O(log n)

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
#include <stdio.h> 
#include <string.h> 
#define MAXN 100000
int BIT[MAXN + 5];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, a, b, y;
    char cmd[8];
    while (scanf("%d", &n) == 1 && n) {
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'B') {
                scanf("%d %d %d", &a, &b, &y);
                modify(a, y, MAXN);
                modify(b + 1, -y, MAXN);
            } else {
                scanf("%d", &a);
                int ret = query(a);
                printf("%d\n", ret);
            }
        }
    }
    return 0;
}
/*
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
0
*/
Read More +
解題區/解題區 - UVa

UVa 745 - Numeric Puzzles Again

Problem

給定七巧板拼圖，保證每一個拼圖都會在最後的盤面上，並且每一個拼圖不可旋轉。

但是在輸出的時候，選擇一個最大權重的表示法進行輸出，同時每組測資保證最多一種同構解。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7
6
3333
33
3333
 33
 33
7  7
7  7
7777
88888
 6
666
 66
  22
222
  2
  5
 55
 55
555
5 5
#
0

Sample Output

1
2
3
4
5
6
7
8777333
8733333
8733323
8777323
8655222
6665552
6655555

Solution

轉換成精準覆蓋問題，套用 DLX 做法來完成。

特別小心輸出的表示法，計算權重時，有可能會有嚴重的 overflow，可以用大數比大小、或者 double 來完成。

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
char pattern[32][4][32][32]; // [id][rotate][x][y]
char prob_out[4][32][32], out[32][32];
int n, m;
int mx[30];
void out_update() {
    int mxrt = -1;
    for (int rt = 1; rt < 4; rt++) {
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++) {
                prob_out[rt][p][q] = prob_out[rt-1][q][n - 1 - p];
            }
        }
    }
    for (int rt = 0; rt < 4; rt++) {
        int sum[30] = {};
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++)
                sum[q] += prob_out[rt][p][n - q - 1] - '0';
        }
        for (int p = 0; p < 29; p++)
            sum[p+1] += sum[p]/10, sum[p] %= 10;
        int flag = 0;
        for (int p = 29; p >= 0; p--) {
            if (sum[p] != mx[p]) {
                flag = sum[p] > mx[p] ? 1 : -1;
                break;
            }
        }
        if (flag == 1) {
            for (int p = 29; p >= 0; p--)
                mx[p] = sum[p];
            mxrt = rt;
        }
    }
    if (mxrt >= 0) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) 
                out[i][j] = prob_out[mxrt][i][j];
    }
}
class DLX {
    public:
    struct DancingLinks {
        int left, right, up, down, ch;
        int id, rotate, px, py; // extra data
    } DL[131072 + 256];
    int s[512], o[512], head, size;		
    void remove(int c) {
        DL[DL[c].right].left = DL[c].left;
        DL[DL[c].left].right = DL[c].right;
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].right; j != i; j = DL[j].right) {
                DL[DL[j].down].up = DL[j].up;
                DL[DL[j].up].down = DL[j].down;
                s[DL[j].ch]--;
            }
        }
    }
    void resume(int c) {
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].left; j != i; j = DL[j].left) {
                DL[DL[j].down].up = j;
                DL[DL[j].up].down = j;
                s[DL[j].ch]++;
            }
        }
        DL[DL[c].right].left = c;
        DL[DL[c].left].right = c;
    }
    int found;
    void print(int dep) {
        for (int i = 0; i < dep; i++) {
            int id = DL[o[i]].id, rt = DL[o[i]].rotate;
            int px = DL[o[i]].px, py = DL[o[i]].py;
            for (int p = 0; p < n; p++) {
                for (int q = 0; q < n; q++) {
                    if (pattern[id][rt][p][q] != ' ')
                        prob_out[0][px + p][py + q] = pattern[id][rt][p][q];
                }
            }
        }
        out_update();
    }
    void dfs(int dep) {
        if (found) return;
        if (DL[head].right == head) {
        	print(dep);
            found++;
            return;
        }
        int tmp = 0x3f3f3f3f, c, i, j;
        for(i = DL[head].right; i != head; i = DL[i].right)
            if(s[i] < tmp)
                tmp = s[i], c = i;
        remove(c);
        for(i = DL[c].down; i != c; i = DL[i].down) {
            o[dep] = i;
            for(j = DL[i].right; j != i; j = DL[j].right)
                remove(DL[j].ch);
            dfs(dep+1);
            for(j = DL[i].left; j != i; j = DL[j].left)
                resume(DL[j].ch);
        }
        resume(c);
    }
    int getnode(int u, int d, int l, int r) {
        DL[size].up = u, DL[size].down = d;
        DL[size].left = l, DL[size].right = r;
        DL[u].down = DL[d].up = DL[l].right = DL[r].left = size;
        assert(size < 131072);
        return size++;
    }
    void newrow(int r[], int rn, int id, int rotate, int px, int py) {
        int i, j, h;
        for(i = 0; i < rn; i++) {
            DL[size].ch = r[i], s[r[i]]++;
            DL[size].id = id; // extra data
            DL[size].rotate = rotate; // extra data
            DL[size].px = px; // extra data
            DL[size].py = py; // extra data
            if(i) {
                j = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, DL[h].left, h);
            } else {
                h = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, size, size);
            }
        }
    }
    void init(int c) {// total column
        size = 0;
        head = getnode(0,0,0,0);
        int i;
        for(i = 1; i <= c; i++) {
            getnode(i, i, DL[head].left, head);
            DL[i].ch = i, s[i] = 0;
        }
    }
} DLX;
int validPos(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n; 
}
char in[32767][128];
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        while (getchar() != '\n');
        DLX.init(n * n + m);
        
        int t = 0;
        while (gets(in[t]) && in[t][0] != '#') {
            t++;
        }
        memset(pattern, ' ', sizeof(pattern));
        
        int test = 0;
        for (int i = 0, idx = 0; i < m; i++) {
            int r = 0, c = 0;
            char label = -1;
            for (int j = 0; in[idx][j]; j++)
                if (in[idx][j] >= '0' && in[idx][j] <= '9')
                    label = in[idx][j];
                    
            for (r = 0; ; r++) {
                int ok = 0;
                for (int j = 0; in[idx][j]; j++)
                    if (in[idx][j] == label)
                        ok = 1;
                if (ok == 0)	break;
                for (int j = 0; in[idx][j]; j++) {
                    if (in[idx][j] == label) {
                        pattern[i][0][r][j] = in[idx][j];
                        c = max(c, j + 1);
                        test++;
                    }
                }
                idx++;
            }
            r = c = max(r, c);
            assert(r <= n && c <= n && r > 0);
            for (int rt = 1; rt < 4; rt++) {
                for (int p = 0; p < r; p++) {
                    for (int q = 0; q < c; q++) {
                        pattern[i][rt][p][q] = pattern[i][rt-1][q][r - 1 - p];
                    }
                }
            }
            for (int rt = 0; rt < 1; rt++) {
                for (int p = -20; p <= n; p++) { 
                    for (int q = -20; q <= n; q++) { // top-left corner
                        int ok = 1, row[512], rn = 0;
                        for (int p1 = 0; p1 < r && ok; p1++) {
                            for (int q1 = 0; q1 < c && ok; q1++) {
                                if (pattern[i][rt][p1][q1] != ' ') {
                                    ok &= validPos(p1 + p, q1 + q);
                                    row[rn++] = (p1 + p) * n + (q1 + q) + 1;
                                }
                            }
                        }
                        if (ok) {
                            row[rn++] = n * n + i + 1;
                            DLX.newrow(row, rn, i, rt, p, q);
                        }
                    }
                }	
            }
//			for (int kind = 0; kind < 4; kind++) {
//				for (int p = 0; p < r; p++, puts("")) {
//					for (int q = 0; q < c; q++)
//						printf("%c", pattern[i][kind][p][q]);
//				}
//				puts("---");
//			}
        }
        memset(mx, 0, sizeof(mx));
        DLX.found = 0;
        DLX.dfs(0);
        assert(DLX.found && test == n*n);
        if (DLX.found) {
            for (int i = 0; i < n; i++, puts("")) {
                for (int j = 0; j < n; j++) {
                    putchar(out[i][j]);
                    assert(out[i][j] != ' ');
                }
            }
        }
        puts("");
    }
    return 0;
}
Read More +