首页 > 代码库 > UVALive 6663 Count the Regions --离散化+DFS染色

UVALive 6663 Count the Regions --离散化+DFS染色

2024-07-16 08:23:42   221人阅读

题意：给你n(n<=50)个矩形（左上角坐标和右下角坐标），问这些矩形总共将平面分成多少个部分。坐标值可能有1e9.

分析：看到n和坐标的范围，容易想到离散化，当时就没想到离散化以后怎么判断区域个数。后来看别人代码才知道，可以将边界上的点vis赋为1，那么枚举所有哈希后的平面上的点，遇到一个vis=0的点就从这点一直搜过去，搜到边界自动会停止了，因为边界vis=1，并且ans++，就可以了。真是太弱。。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <map>using namespace std;#define N 207vector<int> vx,vy;map<int,int> hx,hy;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int vis[N][N];int l[55],r[55],t[55],b[55];bool OK(int nx,int ny){    if(nx >= 0 && nx <= 201 && ny >= 0 && ny <= 201 && !vis[nx][ny])        return 1;    return 0;}void dfs(int x,int y){    vis[x][y] = 1;    for(int k=0;k<4;k++)    {        int nx = x + dx[k];        int ny = y + dy[k];        if(OK(nx,ny))            dfs(nx,ny);    }}int main(){    int n,i,j;    while(scanf("%d",&n)!=EOF && n)    {        vx.clear();vy.clear();        hx.clear();hy.clear();        for(i=0;i<n;i++)        {            scanf("%d%d%d%d",&l[i],&t[i],&r[i],&b[i]);            vx.push_back(l[i]);            vx.push_back(r[i]);            vy.push_back(t[i]);            vy.push_back(b[i]);        }        sort(vx.begin(),vx.end());        vx.erase(unique(vx.begin(),vx.end()),vx.end());  //运用STL巧妙去重        sort(vy.begin(),vy.end());        vy.erase(unique(vy.begin(),vy.end()),vy.end());        for(i=0;i<vx.size();i++)  //以2为间隔，防止出现面积为1的小矩形计算不到的情况            hx[vx[i]] = 2*i+1;        for(i=0;i<vy.size();i++)            hy[vy[i]] = 2*i+1;        for(i=0;i<n;i++)  //离散后的值        {            l[i] = hx[l[i]];            t[i] = hy[t[i]];            r[i] = hx[r[i]];            b[i] = hy[b[i]];        }        memset(vis,0,sizeof(vis));        for(i=0;i<n;i++)    //边界赋值        {            for(j=b[i];j<=t[i];j++)            {                vis[j][l[i]] = 1;                vis[j][r[i]] = 1;            }            for(j=l[i];j<=r[i];j++)            {                vis[t[i]][j] = 1;                vis[b[i]][j] = 1;            }        }        int cnt = 0;        for(i=0;i<=201;i++)        {            for(j=0;j<=201;j++)            {                if(!vis[i][j])                {                    cnt++;                    dfs(i,j);                }            }        }        printf("%d\n",cnt);    }    return 0;}
View Code

 


联系
我们