首页 > 其他分享 >D - LRUD Instructions -- ATCODER

D - LRUD Instructions -- ATCODER

时间:2022-10-26 09:00:53浏览次数:51  
标签:ATCODER ci LRUD -- pos int vector ri cout

D - LRUD Instructions

https://atcoder.jp/contests/abc273/tasks/abc273_d

 

分析

横坐标和纵坐标很大,不能采用二维数组形式,否则内存干爆,

目标对象移动,按照指令进行移动, 每次沿垂直或者水平方向,

那么这里对每一个墙, 都记录两点,即可满足判断需求:

  1. 每个水平方向上的障碍
  2. 每个竖直方向上的障碍

使用map<int, vector<int>>, 然后对vector<int>进行sort

最后在目标移动的使用,在vector<int>中使用upper_bound判断其位置。

 

Code

https://atcoder.jp/contests/abc273/submissions/35962591

int h,w;
int rs, cs;
int n, q;
map<int, vector<int>> xblocks;
map<int, vector<int>> yblocks;
 
int main()
{
    cin >> h >> w;
    cin >> rs >> cs;
    cin >> n;
    
    /*
        store x-direction blocks, i.e. ci
        store y-direction blocks, i.e. ri
    */
    for(int i=0; i<n; i++){
        int ri, ci;
        cin >> ri >> ci;
        vector<int>& tempx = xblocks[ri];
        tempx.push_back(ci);
        
        vector<int>& tempy = yblocks[ci];
        tempy.push_back(ri);
    }
 
    /*
    sort all blocks of each x-directions
    */
    map<int, vector<int>>::iterator it;
    for(it=xblocks.begin(); it!=xblocks.end(); it++){
        vector<int>& block_list = it->second;
        
        sort(block_list.begin(), block_list.end());
    }
 
    /*
    sort all blocks of each y-directions
    */
    for(it=yblocks.begin(); it!=yblocks.end(); it++){
        vector<int>& block_list = it->second;
 
        sort(block_list.begin(), block_list.end());
    }
 
    cin >> q;
    // ri ci are position where T is moving
    int ri = rs;
    int ci = cs;
    for(int i=0; i<q; i++){
        string di;
        int li;
        cin >> di >> li;
        
        // horizontal blocks
        vector<int>& hb = xblocks[ri];
 
        // vertical blocks
        vector<int>& vb = yblocks[ci];
 
        vector<int>::iterator low, up;
        
        if (di == "L"){
            // no block in that row
            if(hb.size() == 0){
//                cout << "ci = " << ci << endl;
//                cout << "li = " << li << endl;
                int pos = ci - li;
                ci = pos>0?pos:1;
                cout << ri << " " << ci << endl;
                continue;
            }
            
            int first = hb[0];
            int last = hb[hb.size()-1];
            if (ci < first){
                int pos = ci - li;
                ci = pos>0?pos:1;
                cout << ri << " " << ci << endl;
                continue;
            }
            
            if (ci > last){
                int pos = ci - li;
                ci = pos>last?pos:(last+1);
 
                cout << ri << " " << ci << endl;
                continue;
            }
            
            up = upper_bound(hb.begin(), hb.end(), ci);
            int upindex = up - hb.begin();
            int base = hb[upindex-1];
            int pos = ci - li;
            ci = pos>base?pos:(base+1);
            
            cout << ri << " " << ci << endl;
        } else if (di == "R") {
            // no block in that row
            if(hb.size() == 0){
                int pos = ci + li;
                ci = pos<=w?pos:w;
                cout << ri << " " << ci << endl;
                continue;
            }
 
            int first = hb[0];
            int last = hb[hb.size()-1];
            if (ci < first){
                int pos = ci + li;
                ci = pos<first?pos:(first-1);
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            if (ci > last){
                int pos = ci + li;
                ci = pos<=w?pos:w;
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            up = upper_bound(hb.begin(), hb.end(), ci);
            int upindex = up - hb.begin();
            int top = hb[upindex];
            int pos = ci + li;
            ci = pos<top?pos:top-1;
 
            cout << ri << " " << ci << endl;
        } else if (di == "U") {
            // no block in that column
            if(vb.size() == 0){
                int pos = ri - li;
                ri = pos>0?pos:1;
                cout << ri << " " << ci << endl;
                continue;
            }
 
            int first = vb[0];
            int last = vb[vb.size()-1];
            if (ri < first){
                int pos = ri - li;
                ri = pos>0?pos:1;
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            if (ri > last){
//                cout << "ri = " << ri << endl;
//                cout << "li = " << li << endl;
//                cout << "last = " << last << endl;
                
                int pos = ri - li;
                ri = pos>last?pos:(last+1);
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            up = upper_bound(vb.begin(), vb.end(), ri);
            int upindex = up - vb.begin();
 
            int top = vb[upindex-1];
            int pos = ri - li;
            ri = pos>top?pos:(top+1);
            
            cout << ri << " " << ci << endl;
        } else if (di == "D") {
            // no block in that column
            if(vb.size() == 0){
                int pos = ri + li;
                ri = pos<=h?pos:h;
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            int first = vb[0];
            int last = vb[vb.size()-1];
            if (ri < first){
                int pos = ri + li;
                ri = pos<first?pos:(first-1);
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            if (ri > last){
                int pos = ri + li;
                ri = pos<=h?pos:h;
 
                cout << ri << " " << ci << endl;
                continue;
            }
 
            up = upper_bound(vb.begin(), vb.end(), ri);
            int upindex = up - vb.begin();
 
            int top = vb[upindex];
            int pos = ri + li;
            ri = pos<top?pos:(top-1);
 
            cout << ri << " " << ci << endl;
        }
    }
 
    return 0;
}

 

标签:ATCODER,ci,LRUD,--,pos,int,vector,ri,cout
From: https://www.cnblogs.com/lightsong/p/16827094.html

相关文章

  • 深拷贝的几种方法
    一:递归调用<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewp......
  • pipeline xargs命令
    linuxxargs命令的n1参数xargs(英文全拼:eXtendedARGuments)是给命令传递参数的一个过滤器,也是组合多个命令的一个工具。xargs可以将管道或标准输入(stdin)数据转换成命......
  • 实验三
      #include<iostream>usingstd::cout;usingstd::endl;//类A的定义classA{public:A(intx0,inty0):x{x0},y{y0}{}voidshow()const{cout<<......
  • TLS1.0的加密方式升级成TSL 1.2的方法
    Theconnectionusedtoloadresourcesfromhttps://www.xxx.netusedTLS1.0orTLS1.1,whicharedeprecatedandwillbedisabledinthefuture.Oncedisabled......
  • 消息队列之RabbitMQ介绍与运用
    RabbitMQ说明本章,我们主要从RabbitMQ简介、RabbitMQ安装、RabbitMQ常用命令、RabbitMQ架构模式、RabbitMQ使用、Quick.RabbitMQPlus的使用和RabbitMQ总结这几个方面对R......
  • 植被指数第三弹-色素
    植被指数第三弹—叶、色素与光目录植被指数第三弹—叶、色素与光叶片色素光谱特征色素指数1PRI(PhotochemicalReflectionIndex)2PSRI(PlantSenescenceReflectancei......
  • (转)centos没有ip
    原:https://blog.csdn.net/qq_45740349/article/details/116408585 新安装的CentOS,输入ipaddr命令可以发现没有ip地址:     解决方法如下:Step1:执行下面的......
  • 测试架构师应该做和不应该做的事情
    内容大纲原文解读测试架构师是产品测试专家,是测试团队的灵魂人物,也是测试工程师在软件测试技术上的一个重要发展方向。在需求分析阶段,首先要理解产品的商业目标和核心......
  • 实验(3)
    实验5task_5.cpp1#include"info.hpp"2#include<vector>3//#include<iomanip>45intmain(){6usingnamespacestd;7constintcapacity=1......
  • NFS共享文件
    NFS共享文件服务端安装NFS[root@localhostwww]yum-yinstallnfs-utilsrpcbind创建需要共享的文件夹share[root@localhost/]mkdir-p/www/share编辑/......