2010年02月21日星期日.sgu177 平面四叉樹
This is my first problem solving report in English,sorry for my poor English.
sgu177: I know 3 ways to solve this problem.
1.quad tree of plane :this is a good and straight forward solution
2.segment trees covers segment trees :less efficient than quadtree,but easy to implement
3.with the special characteristic of this problem,we can dye the plane with opposite
order of the input,and if one grid is colored it cannot be colored again.
The 1st solution can be used extensively.
Quite a lot of the plane query problem can be solve by it.And it also have more
applications in real, such as 3D game programming,computational geometry.
So if you don't know it,I suggest you look the code below.It will be helpful
Though the solution is quite slow in this problem....
The 3rd solution is very smart,you can look here
http://www.briefdream.com/sgu-177/
for a complete code.
I think the original intention of this problem is to practice quadtree,the memory is
just OK when I used quadtree.
sgu177：就我所知，此題有3中解法。
1.平面四叉樹：這是一個平面問題的直覺通解。
2.線段樹套樹，更好寫一點，效率稍差，只是常數級別的差距。
3.倒序染色。從后向前染色，如果一個格子已經被染過色的，那么就不必再被染第二遍。
利用這個性質，可以得到一個聰明的解法。具體代碼看這里。
http://www.briefdream.com/sgu-177/
我認為這題的本意就是為了練習一下四叉樹，四叉樹再平面詢問的問題上，可以有非常多的應用。
有些需要很巧妙的思考的問題可以直接用四叉樹暴力。
而且四叉樹在編碼，計算幾何，計算機圖形學，游戲編程上都有很廣泛的應用，有可能的話，我
建議自己實現一下。
本題內存比較緊，int超內存的話，可以用short搞一下。
?1?
?2?const?int?N?=?1001;
?3?struct?node?{
?4?????short?ux,?uy,?dx,?dy;
?5?????char?c;
?6?????node?*pt[4];
?7?}?pool[N?*?N?*?2],?*root;
?8??
?9?int?top,?n,?m;
10?void?build(node?*?root,?short?ux,?short?uy,?short?dx,?short?dy)
11?{
12???//root->c?=?0;
13???root->ux?=?ux;
14???root->uy?=?uy;
15???root->dx?=?dx;
16???root->dy?=?dy;
17???if?(ux?==?dx?&&?uy?==?dy)?{?return;?}
18?
19???short?mx?=(ux?+?dx)?>>?1;
20???short?my?=(uy?+?dy)?>>?1;
21???build(root->pt[0]?=?&pool[top++],?ux,?uy,?mx,?my);
22???if?(uy?!=?dy)?{?build(root->pt[1]?=?&pool[top++],?ux,?my?+?1,?mx,?dy);?}
23???if?(ux?!=?dx)?{?build(root->pt[2]?=?&pool[top++],?mx?+?1,?uy,?dx,?my);?}
24???if?(ux?!=?dx?&&?uy?!=?dy)?{
25???????build(root->pt[3]?=?&pool[top++],?mx?+?1,?my?+?1,?dx,?dy);
26???}
27?}
28?
29?char?color;
30?int?x0,x1,y0,y1;
31?const?int?NEG?=?2;
32?void?dye(node?*?root)
33?{
34???if?(root?==?0)?{?return;?}
35???if?(x0?>?root->dx?||?x1?<?root->ux?||
36???????y0?>?root->dy?||?y1?<?root->uy)?{?//fast?exclude
37???????return;
38???}
39???if?(x0?<=?root->ux?&&?x1?>=?root->dx?&&
40???????y0?<=?root->uy?&&?y1?>=?root->dy)?{?//complete?cover
41???????root->c?=?color;
42???????return;
43???}
44???for?(int?i?=?0;i?<?4;i++)?{?//half?cover
45???????if?(root->pt[i])?{
46???????????/*?I?think?it?is?the?fatal?statement?which?is?used?to?expand?the?root?color
47????????????*?to?the?desendants?*/
48???????????if?(root->c?!=?NEG)?{????
49???????????????root->pt[i]->c?=?root->c;
50???????????}
51???????????dye(root->pt[i]);
52???????}
53???}
54???if?(root->c?!=?NEG)?{
55???????root->c?=?NEG;
56???}
57?}
58//http://www.shnenglu.com/schindlerlee/
59?int?statics(node?*?root)
60?{
61???if?(root)?{
62???????int?res?=?0;
63???????if?(root->c?==?NEG)?{
64???????????for?(int?i?=?0;i?<?4;i++)?{
65???????????????res?+=?statics(root->pt[i]);
66???????????}
67???????}else?if?(root->c?==?0)?{
68???????????res?=?(root->dy?-?root->uy?+?1)?*?(root->dx?-?root->ux?+?1);
69???????}
70???????return?res;
71???}
72???return?0;
73?}
74?
75?int?main()
76?{
77???int?i,?j,?k,?ux,uy,dx,dy;
78???char?c;
79???scanf("%d%d",?&n,?&m);
80???root?=?&pool[top++],?build(root,?1,?1,?n,?n);
81???while?(m--)?{
82???????scanf("%d?%d?%d?%d?%c",&ux,&uy,&dx,&dy,&c);
83???????color?=?(c?==?'b');
84???????x0?=?min(ux,dx),?x1?=?max(ux,dx);
85???????y0?=?min(uy,dy),?y1?=?max(uy,dy);
86???????dye(root);
87???}
88???printf("%d\n",statics(root));
89???return?0;
90?}
91?
92??