HDU - 6665 Calabash and Landlord（离散化 + dfs）

Calabash is the servant of a landlord. The landlord owns a piece of land, which can be regarded as an infinite 2D plane. 

One day the landlord set up two orthogonal rectangular-shaped fences on his land. He asked Calabash a simple problem: how many nonempty connected components is my land divided into by these two fences, both finite and infinite? Calabash couldn't answer this simple question. Please help him! 

Recall that a connected component is a maximal set of points not occupied by the fences, and every two points in the set are reachable without crossing the fence. 

Input

The first line of input consists of a single integer T (1≤T≤10000), the number of test cases. 

Each test case contains two lines, specifying the two rectangles. Each line contains four integers x1,y1,x2,y2 (0≤x1,y1,x2,y2≤109,x1<x2,y1<y2), where (x1,y1),(x2,y2) are the Cartesian coordinates of two opposite vertices of the rectangular fence. The edges of the rectangles are parallel to the coordinate axes. The edges of the two rectangles may intersect, overlap, or even coincide. 

Output

For each test case, print the answer as an integer in one line.

Sample Input

3
0 0 1 1
2 2 3 4
1 0 3 2
0 1 2 3
0 0 1 1
0 0 1 1

Sample Output

3
4
2

题意：

给两个矩形的左下角坐标和右上角坐标，问这两个矩形将平面分成几个非空部分

思路：

将矩形坐标离散化，构造一个离散化后的矩阵来表示平面，矩形边界的位置标记为1，即不可走，然后dfs搜索连通块即可

细节见注释

参考https://blog.csdn.net/intmainhhh/article/details/99629084

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 7;

int x[5], y[5], a[5], b[5];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
bool mp[11][11];

void dfs(int x, int y)
{
    mp[x][y] = 1;
    for(int i = 0; i < 4; ++i)
    {
        int fx = x + dir[i][0];
        int fy = y + dir[i][1];
        if(fx >= 0 && fx < 11 && fy >= 0 && fy < 11 && !mp[fx][fy])
        {
            dfs(fx, fy);
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        for(int i = 1; i <= 4; ++i)
        {
            scanf("%d%d", &x[i], &y[i]);
            a[i] = x[i];
            b[i] = y[i];
        }
        sort(a + 1, a + 5);    //排序
        sort(b + 1, b + 5);
        for(int i = 1; i <= 4; ++i)    //离散化，乘以2是为了避免矩形长或宽是1，导致矩形内部无法搜到
        {
            x[i] = 2 * (lower_bound(a + 1, a + 5, x[i]) - a);
            y[i] = 2 * (lower_bound(b + 1, b + 5, y[i]) - b);
        }
        memset(mp, 0, sizeof(mp));
        //矩形边界赋为1
        for(int i = x[1]; i <= x[2]; ++i) mp[i][y[1]] = mp[i][y[2]] = 1;
        for(int i = x[3]; i <= x[4]; ++i) mp[i][y[3]] = mp[i][y[4]] = 1;
        for(int i = y[1]; i <= y[2]; ++i) mp[x[1]][i] = mp[x[2]][i] = 1;
        for(int i = y[3]; i <= y[4]; ++i) mp[x[3]][i] = mp[x[4]][i] = 1;
        int ans = 0;
        for(int i = 0; i < 11; ++i)
        {
            for(int j = 0; j < 11; ++j)
            {
                if(!mp[i][j])
                {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}
/*
4
0 0 1 1
1 0 2 1
0 0 1 1
2 2 3 4
1 0 3 2
0 1 2 3
0 0 1 1
0 0 1 1
*/