坐标离散化(挑战程序设计竞赛)

逃离我推掉我的手 2022-12-28 12:45 174阅读 0赞

### 文章目录 ###

*  坐标离散化
 *   *  题目描述
     *  算法思路
     *  挑战程序书中代码
     *  代码解疑
     *  解题代码

--------------------

# 坐标离散化 #

当区域的坐标很大时，无法直接使用搜索算法，但是图可以通过缩放，达到同样的效果。

这种坐标缩放，就称为坐标离散化

## 题目描述 ##

![1][]

## 算法思路 ##

书上给的样例太坑了，你会发现最后这个样例，根本没有离散化

所以这里给出另一组样例：

10 10 4
    2 2 8 2
    2 8 8 8
    3 3 3 8
    8 3 8 8

这个样例的变换结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

## 挑战程序书中代码 ##

#include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    #define MAX_N 99
    //输入
    int W, H, N;
    int X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N];
    
    //填充用
    bool fld[MAX_N * 6][MAX_N * 6];
    
    //广搜方向
    int dx[4] = {
        1, 0, -1, 0};
    int dy[4] = {
        0, -1, 0, 1};
    
    //对x1和x2进行坐标离散化，并返回离散化之后的宽度
    int compress(int *x1, int *x2, int w)
    {
        
        vector<int> xs;
      
      	//将墙的前后包括自己，这三个列（或行）加入vector中
        for(int i = 0; i < N; i++){
        
            for(int d = -1; d <= 1; d++){
        
            int tx1 = x1[i] + d, tx2 = x2[i] + d;
                if(1 <= tx1 && tx1 <= w) xs.push_back(tx1);
                if(1 <= tx2 && tx2 <= w) xs.push_back(tx2);
            }
        }
        
      	//去重
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
      	//去重
        
      	//坐标离散化
        for(int i = 0; i < N; i++){
        
            x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
            x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
        }
      	//坐标离散化
        
        return xs.size();
    }
    
    
    void solve()
    {
        
        //坐标离散化
        W = compress(X1, X2, W);
        H = compress(Y1, Y2, H);
        
        //填充有直线的部分
        memset(fld, 0, sizeof(fld));
        for(int i = 0; i < N; i++){
        
            for(int y = Y1[i]; y <= Y2[i]; y++){
        
                for(int x = X1[i]; x <= X2[i]; x++)
                    fld[x][y] = true;
            }
        }
        
        //求区域的个数
        int ans = 0;
        for(int y = 0; y < H; y++)
            for(int x = 0; x < W; x++){
        
                if(fld[y][x])
                    continue;
                ans++;
                
                //宽度优先搜索
                queue<pair<int, int>> que;
                que.push(make_pair(x, y));
                while(!que.empty()){
        
                    int sx = que.front().first, sy = que.front().second;
                    que.pop();
                    
                    for(int i = 0; i < 4; i++){
        
                        int tx = sx + dx[i], ty = sy + dy[i];
                        if(tx < 0 || W <= tx || ty < 0 || H <= ty) continue;
                        if(fld[ty][tx]) continue;
                        que.push(make_pair(tx, ty));
                        fld[ty][tx] = true;
                    }
                }
            }
        
        printf("%d\n", ans);
    }

## 代码解疑 ##

**1、unique()函数是STL中的常用函数。**

**函数的作用是“删除”序列中所有相邻的重复元素**，但是这里的 **“删除”是将重复元素的位置被不重复元素占领** ，因此一般unique()函数在使用前都会进行排序。**返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素**

**2、xs.erase(unique(xs.begin(), xs.end()), xs.end());**

因为unique()返回**去重后容器中不重复序列的最后一个元素的下一个元素**，所以用unique()函数的返回值减去xs.end()就是所有重复的元素。

## 解题代码 ##

代码来源：https://blog.csdn.net/qq\_27601815/article/details/70232435?utm\_source=distribute.pc\_relevant.none-task

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<vector>
    using namespace std;
    int x1[555],x2[555],y1[555],y2[555];//开始列号结束列号，开始行号，结束行号
    int w,h,n,ans;//宽，高，以及横线的个数
    int line[555*6][555*6];
    int dire[4][2]={
        -1,0,1,0,0,-1,0,1};
    struct node{
        int x,y;};
    int compress(int *xx1,int *xx2,int w)//开始坐标，结束坐标
    {
        
        vector<int>v;
        
        for(int i=0;i<n;i++)//将横线本身以及附近两横线存储
        for(int d=-1;d<=1;d++)
        {
        
            int nx1=xx1[i]+d;int nx2=xx2[i]+d;
            if(nx1>=1&&nx1<=w) v.push_back(nx1);
            if(nx2>=1&&nx2<=w) v.push_back(nx2);
        }
      
        //去重
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
         
        //离散化后的坐标
        for(int i=0;i<n;i++)
        {
        
            xx1[i]=find(v.begin(),v.end(),xx1[i])-v.begin();
            xx2[i]=find(v.begin(),v.end(),xx2[i])-v.begin();
         }
        return v.size();
    }
     
    //常规广搜
    void bfs(int xx,int yy)
    {
        
        queue<node>q;
        q.push(node{
        xx,yy});
        line[xx][yy]=1;
        
        while(!q.empty())
        {
        
            node t=q.front();q.pop();
            int x=t.x;int y=t.y;
            
            for(int i=0;i<4;i++)
            {
        
                int nx=x+dire[i][0];
                int ny=y+dire[i][1];
                if(nx<0||nx>=h||ny<0||ny>=w)continue;
                if(!line[nx][ny])
                {
        
                    line[nx][ny]=1;
                    q.push(node{
        nx,ny});
                }
            }
        }
    }
    
    int main()
    {
        
        while(cin>>w>>h>>n)
        {
        
            ans=0;memset(line,0,sizeof(line));
            
            for(int i=0;i<n;i++)cin>>x1[i];
            for(int i=0;i<n;i++)cin>>x2[i];
            for(int i=0;i<n;i++)cin>>y1[i];
            for(int i=0;i<n;i++)cin>>y2[i];
             
          	//离散化后的宽和高
             w=compress(x1,x2,w);
             h=compress(y1,y2,h);
            
            //标记上所在横线上的点
            for(int i=0;i<n;i++)//枚举n条横线
            for(int y=y1[i];y<=y2[i];y++)//枚举行
            for(int x=x1[i];x<=x2[i];x++)//枚举列
            {
        
                line[y][x]=1;
             }
             
             //打印查看离散化后的图形
    //
    //         for(int i=0;i<h;i++)
    //         {
        
    //             for(int j=0;j<w;j++)
    //             {
        
    //                 if(line[i][j])cout<<1<<" ";
    //                 else cout<<0<<" ";
    //             }
    //             cout<<endl;
    //         }
    //         cout<<endl<<ans<<endl;
             
              //搜索求区域块数 防止爆栈，这里使用广搜
             for(int i=0;i<h;i++)
             for(int j=0;j<w;j++)
             {
        
                 if(!line[i][j]){
        
                     ans++;
                     bfs(i,j);
                 }
              }
              cout<<ans<<endl;
        }
        
        return 0;
     }
     /*
    10 10 5
    1 1 4 9 10
    6 10 4 9 10
    4 8 1 1 6
    4 8 10 5 10
    */

[1]: /images/20221120/aad8e79fb41947dd92ae973e08d1379a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201217105027914.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70