首页 > 搜索 > DFS搜索 > HDU 4429-Split the Rectangle-图-[解题报告]HOJ
2015
07-16

HDU 4429-Split the Rectangle-图-[解题报告]HOJ

Split the Rectangle

问题描述 :

Alice comes up with a new game and wants to play with Bob.
There is one rectangle on the paper initially, we define its lower-left corner’s coordinate is (xL, yL) and upper-right corner’s coordinate is (xR, yR).
Bob has executed the step as description below N times:
Bob should select one empty rectangle. If the rectangle is the initial one or is split by one vertical segment, he should split it into two parts by drawing one horizontal segment; otherwise he should split the rectangle into two parts by drawing one vertical segment. An empty rectangle means there is no segment in this rectangle except its only four boundary segments.
You should pay attention that there are only two kinds segments: vertical segment and horizontal segment.
Now Bob has several queries. In each query, Bob selects two target points in the paper. (You can assume that all given target points are always located inside the initial rectangle and not in any drawing segments.) He wants Alice to answer the question as soon as possible: Alice can erase several existing segments, and make two target points in one empty rectangle, and she should answer how many empty rectangles at most would be left at last.
But there are some restrictions: Alice cannot erase segments of the initial rectangle (the (xL, yL) to (xR, yR) one), she can only erase segments drew by Bob; if Alice want to erase one segment, both sides of the segment must be empty rectangles, and after erase it, the two empty rectangles must combine to one bigger empty rectangle; if erasing an existing segment will lead to a disconnected graph, the operation is forbidden.
Polaris of Pandora

输入:

There are multiple test cases.
The first line contains four integers xL, yL, xR, yR indicating the coordinates of the lower-left corner and the upper-right corner of the initial huge rectangle respectively. (-100,000 <= xL, yL, xR, yR <= 100,000, xL< xR, yL< yR)
The next line contains two integers N and Q. (1 <= N, Q <= 1000)
The next N lines each line contains four integers x1, y1, x2, y2 indicating the coordinates of two endpoints of one drawing segments. (-100,000 <= x1, y1, x2, y2 <= 100,000, x1=x2 | y1=y2)
The next Q lines each line contains four integers xA, yA, xB, yB indicating the coordinates of two target points in this query. (-100,000 <= xA, yA, xB, yB <= 100,000).

输出:

There are multiple test cases.
The first line contains four integers xL, yL, xR, yR indicating the coordinates of the lower-left corner and the upper-right corner of the initial huge rectangle respectively. (-100,000 <= xL, yL, xR, yR <= 100,000, xL< xR, yL< yR)
The next line contains two integers N and Q. (1 <= N, Q <= 1000)
The next N lines each line contains four integers x1, y1, x2, y2 indicating the coordinates of two endpoints of one drawing segments. (-100,000 <= x1, y1, x2, y2 <= 100,000, x1=x2 | y1=y2)
The next Q lines each line contains four integers xA, yA, xB, yB indicating the coordinates of two target points in this query. (-100,000 <= xA, yA, xB, yB <= 100,000).

样例输入:

-10 -10 10 10
5 1
-10 0 10 0  
5 -10 5 0
-5 0 -5 10
-5 5 10 5
5 -5 10 -5
0 -3 7 -3
0 0 4 4
3 2
0 2 4 2
2 0 2 2
2 2 2 4
1 1 1 3
1 1 3 1
-10 -10 10 10
3 4
-10 0 10 0
0 -10 0 0
0 0 0 10
-9 -9 -8 -8
-9 -9 -9 9
-9 -9 9 -9
-9 -9 9 9

样例输出:

4
1
3
4
1
3
1

题目:

http://acm.hdu.edu.cn/showproblem.php?pid=4429

题意:

一个大矩阵中有m条水平或竖直直线,将其分成m+1个小矩阵。有q个询问,输入两个点,要使得两个点在同一个矩阵,可以拿掉一些边,但是拿掉边之后要使得两个矩阵能合成一个矩阵。求出最后剩下的最多的矩阵数量。

思路:

将图转化成树。

大矩阵为根,一条直线分割矩阵,一个矩阵变成根的左儿子,一个矩阵变成根的右儿子。

建完树之后,dfs求解每个节点的子节点个数num。

对于每个询问,暴力求解lca,则答案为m+1- num【lca】+1.

AC.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int maxn = 2005;
struct Node {
    int lx, ly, rx, ry;
    int fath, lson, rson, dep;
}node[maxn];

int find(int x, int y)
{
    int r = 0, t;
    while(1) {
        if(node[r].lson == 0) return r;
        t = node[r].lson;
        if(x >= node[t].lx && x <= node[t].rx && y >= node[t].ly && y <= node[t].ry)
            r = t;
        else r = node[r].rson;
    }
}
int num[maxn];
int get_num(int u)
{
    num[u] = 0;
    if(node[u].lson == 0) return num[u] = 1;
    else {
        num[u] += get_num(node[u].lson);
        num[u] += get_num(node[u].rson);
    }
    return num[u];
}
int main()
{
    //freopen("in", "r", stdin);
    int lx, ly, rx, ry;
    int m, q;
    while(~scanf("%d%d%d%d", &lx, &ly, &rx, &ry)) {
        int root = 0, tol = 1;
        //memset(node, 0, sizeof(node));

        node[root] = (Node){lx, ly, rx, ry, -1, 0, 0, 0};

        scanf("%d%d", &m, &q);
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
            if(lx > rx) swap(lx, rx);
            if(ly > ry) swap(ly, ry);

            int mx = (lx+rx)/2, my = (ly+ry)/2;
            int pos = find(mx, my);

            int dep = node[pos].dep;
            node[pos].lson = tol;
            node[tol] = (Node){node[pos].lx, node[pos].ly, rx, ry, pos, 0, 0, dep+1};
            tol++;

            node[pos].rson = tol;
            node[tol] = (Node){lx, ly, node[pos].rx, node[pos].ry, pos, 0, 0, dep+1};
            tol++;
        }
        get_num(0);
//        for(int i = 0; i <= tol; ++i) {
//            printf("%d ", num[i]);
//        }
//        puts(" ");
        while(q--) {
            scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
            int g1 = find(lx, ly);
            int g2 = find(rx, ry);
            while(g1 != g2) {
                if(node[g1].dep < node[g2].dep) g2 = node[g2].fath;
                else if(node[g1].dep > node[g2].dep) g1 = node[g1].fath;
                else {
                    g1 = node[g1].fath;
                    g2 = node[g2].fath;
                }
            }
//            printf("%d\n", num[g1]);
            printf("%d\n", m+1 - num[g1]+1);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sotifish/article/details/48533141


, ,