题解：P8070 [BalticOI 2002] Moving Robots (Day2)

zzz13579zzz · 2025-02-28 10:24:16 · 题解

随到的题目，看没有题解，先来一发

P8070 [BalticOI 2002] Moving Robots (Day2)

题目描述

有 R 个机器人在二维平面运动，可前进或转向，删除最小的命令个数，使得所有机器人停在同一位置

数据范围

• 题目分析

  注意到 n 只有 50，所以机器人能走到的位置与初始点的曼哈顿距离不会超过 50，所以可以暴力枚举能走到的位置，计算最少能删多少命令

• 具体实现

  用数组存储每个机器人到达不同位置，朝向不同方向的可删除最小命令数，若不可达，记为 inf

  对于每条命令，机器人上一步可达的位置都会进行此命令，所以遍历一遍数组，进行转移，并将最小命令数 -1

• 细节处理

  2. 方向可以除以 90,变为 0,1,2,3 处理
  3. 不能一边遍历一边修改，否则可能会出现还未遍历到的位置已被修改的情况，建议使用 vector 等先存后用

• 复杂度分析

  R$ 个机器人，$n$ 条命令，约有 $n^2$ 个位置可达，加上 $4$ 个方向，$O(Rn^3)

  code

  写的比较凌乱，看上面比较好

#include<bits/stdc++.h>
using namespace std;
int r,n,x,y,c,ans[11][210][210][4],d,dd[210][210];
struct wz{int x,y,c,w;};
void wd(int r){
    vector<wz>q;
    for(int x=1;x<=200;x++)
        for(int y=1;y<=200;y++)
            for(c=0;c<4;c++)
                if(ans[r][x][y][c]<=n and ans[r][x][y][c]>0){
                    wz kk={x,y,c,ans[r][x][y][c]};
                    q.emplace_back(kk); }                               

    for(auto t:q){
        int x=t.x,y=t.y,c=t.c,w=t.w;
        if(c==0)ans[r][x+1][y][c]=min(ans[r][x+1][y][c],w-1);
        if(c==1)ans[r][x][y+1][c]=min(ans[r][x][y+1][c],w-1);   
        if(c==2)ans[r][x-1][y][c]=min(ans[r][x-1][y][c],w-1);
        if(c==3)ans[r][x][y-1][c]=min(ans[r][x][y-1][c],w-1);           
    }
}
void turn(int r,int d){
    vector<wz>q;
    for(int x=1;x<=200;x++)
        for(int y=1;y<=200;y++)
            for(c=0;c<4;c++)
                if(ans[r][x][y][c]<=n and ans[r][x][y][c]>0){
                    wz kk={x,y,c,ans[r][x][y][c]};
                    q.emplace_back(kk); }
    for(auto t:q){
        int x=t.x,y=t.y,c=t.c,w=t.w;    
        ans[r][x][y][(c+d)%4]=min(ans[r][x][y][(c+d)%4],w-1);
    }       
}
int main(){
    cin>>r;
    for(int i=1;i<=r;i++)
        for(int x=1;x<=200;x++)
            for(int y=1;y<=200;y++){
                for(c=0;c<4;c++)ans[i][x][y][c]=100;
            }
    for(int i=1;i<=r;i++){
        cin>>x>>y>>c>>n;
        x+=100,y+=100,c/=90;
        ans[i][x][y][c]=n;
        for(int k=1;k<=n;k++){
            char s;
            cin>>s;
            if(s=='S'){
                wd(i);
            }else {
                cin>>d;
                d/=90;
                turn(i,d);
            }
        }
    }
    for(int x=1;x<=200;x++)
        for(int y=1;y<=200;y++)
            for(int i=1;i<=r;i++){
                int kk=100;
                for(c=0;c<4;c++)kk=min(kk,ans[i][x][y][c]);
                if(kk>=100){dd[x][y]=-1;break;}
                dd[x][y]+=kk;
            }
    int mi=100,mx=0,my=0;
    for(int x=1;x<=200;x++){
        for(int y=1;y<=200;y++){
            if(dd[x][y]<=mi and dd[x][y]>=0 and dd[x][y]<100){
                mi=dd[x][y];
                mx=x-100,my=y-100;
            }
        }   
    }   
    if(mi==100)cout<<-1;
    else {
        cout<<mi<<endl;
        cout<<mx<<' '<<my;
    }
    return 0;
}