弹指间计算机协会 X Five Pines Robomaster实验室 考核题面与题解(三)

简介: 弹指间计算机协会 X Five Pines Robomaster实验室 考核题面与题解

Sample Input 1

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

Sample Output 1

Yes
No
Yes

Hint

第一组数据,由奶酪的剖面图可见:

第一个空洞在 ( 0 , 0 , 0 )与下表面相切;

第二个空洞在 ( 0 , 0 , 4 ) 与上表面相切;

两个空洞在 ( 0 , 0 , 2 ) 相切。

输出 Yes

第二组数据,由奶酪的剖面图可见:

两个空洞既不相交也不相切。

输出 No

第三组数据,由奶酪的剖面图可见:

两个空洞相交,且与上下表面相切或相交。

输出 Yes

【数据规模与约定】

image.png


题解

建图,设0号点为起点,n+1号点为终点。将每个洞视为图中的点。若洞高度绝对值小于半径r,则起点连到该点。若洞高度大于hr,则该点连到终点。若距离小于半径的两倍,则两个洞所代表的点连一条边。建图完成后,dfs

代码

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
vector<int> G[1005];
double ball[1005][4];
bool st[1005];
void dfs(int i){
  st[i]=1;
  for(auto node:G[i]){
    if (!st[node])
      dfs(node);
  }
}
signed main(){
  freopen("res.in","r",stdin);
  freopen("res.out","w",stdout);
  int t;
  cin>>t;
  while(t--){
    memset(ball,0,sizeof ball);
    memset(st,0,sizeof st);
    int n;
    double h,r;
    cin>>n>>h>>r;
    for(int i=0;i<=n+1;i++)
      G[i].clear(); 
    for(int i=1;i<=n;i++){
      cin>>ball[i][1]>>ball[i][2]>>ball[i][3];
    }
    for(int i=1;i<=n;i++){
      if (ball[i][3]<=r){
        G[0].push_back(i);//0号点为起点,底边
        G[i].push_back(0);
      }
      if (ball[i][3]>=h-r){
        G[n+1].push_back(i);//n+1号点为终点 
        G[i].push_back(n+1);
      }
      for(int j=i+1;j<=n;j++){
        double sqrdst=(ball[i][1]-ball[j][1])*(ball[i][1]-ball[j][1])
              +(ball[i][2]-ball[j][2])*(ball[i][2]-ball[j][2])
              +(ball[i][3]-ball[j][3])*(ball[i][3]-ball[j][3]);
        if (sqrdst<=4*r*r){
          G[i].push_back(j);
          G[j].push_back(i);
        }
      }
    }
    dfs(0);
    if (st[n+1])
      cout<<"Yes\n";
    else
      cout<<"No\n";
  }
}

机器人搬重物

Description

image.png

Output

一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出1

Sample Input 1

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

Sample Output 1

12

题解

image.png

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<map>
#include<iomanip>
using namespace std;
struct posd{
  int x, y, d;
};
int collidx[4] = { -1, 0,-1,0 };//障碍物
int collidy[4] = { -1,-1, 0,0 };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dist[55][55][4];//0 北 1南 2西 3东
map<char, int> c2i = {{'N',0},{'S',1},{'W',2},{'E',3}};
int ditu[55][55];
int n, m;
bool collide(int x, int y) {
  if (x == 0 || y == 0 || x >= n || y >= m)
    return true;
  for (int k = 0;k < 4;k++) {
    int tx = x + collidx[k];
    int ty = y + collidy[k];
    if (ditu[tx][ty] == 1)
      return true;
  }
  return false;
}
int main() {
  cin >> n >> m;
  for (int i = 0;i < n;i++)
    for (int j = 0;j < m;j++)
      cin >> ditu[i][j];
  int startx, starty, endx, endy;
  char startd;
  cin >> startx >> starty >> endx >> endy;
  cin >> startd;
  memset(dist, 0x3f3f3f3f, sizeof dist);
  queue<posd> q;
  q.push({ startx,starty,c2i[startd] });
  dist[startx][starty][c2i[startd]] = 0;
  while (!q.empty()) {
    auto p= q.front();
    q.pop();
    if (p.d == 0 || p.d == 1) {//从南北转到东西
      if (dist[p.x][p.y][2] == 0x3f3f3f3f) {
        dist[p.x][p.y][2] = dist[p.x][p.y][p.d] + 1;
        q.push({ p.x,p.y,2 });
      }
      if (dist[p.x][p.y][3] == 0x3f3f3f3f) {
        dist[p.x][p.y][3] = dist[p.x][p.y][p.d] + 1;
        q.push({ p.x,p.y,3 });
      }
    }
    if (p.d == 2 || p.d == 3) {//从东西转到南北
      if (dist[p.x][p.y][0] == 0x3f3f3f3f) {
        dist[p.x][p.y][0] = dist[p.x][p.y][p.d] + 1;
        q.push({ p.x,p.y,0 });
      }
      if (dist[p.x][p.y][1] == 0x3f3f3f3f) {
        dist[p.x][p.y][1] = dist[p.x][p.y][p.d] + 1;
        q.push({ p.x,p.y,1 });
      }
    }
    //往对应方向走1/2/3步
    int tx = p.x, ty = p.y;
    for (int _ = 0;_ <3;_++) {
      tx +=dx[p.d];
      ty +=dy[p.d];
      if (collide(tx, ty))
        break;
      if (dist[tx][ty][p.d] != 0x3f3f3f3f)
        continue;
      dist[tx][ty][p.d] = dist[p.x][p.y][p.d] + 1;
      q.push({ tx,ty,p.d });
    }
  }
  int res = 0x3f3f3f3f;
  for (int k = 0;k < 4;k++)
    res = min(res, dist[endx][endy][k]);
    if (res==0x3f3f3f3f)
        cout<<-1;
    else 
    cout << res << endl;
}
目录
打赏
0
0
0
0
53
分享
相关文章
【题目】【网络系统管理】2022年江苏省职业院校技能大赛 高职竞赛样题
【题目】【网络系统管理】2022年江苏省职业院校技能大赛 高职竞赛样题
【题目】【网络系统管理】2022年江苏省职业院校技能大赛 高职竞赛样题
【题目】【网络系统管理】2019年全国职业技能大赛高职组计算机网络应用赛项H卷
【题目】【网络系统管理】2019年全国职业技能大赛高职组计算机网络应用赛项H卷
【题目】【网络系统管理】2019年全国职业技能大赛高职组计算机网络应用赛项H卷
【题目】【网络系统管理】2022年甘肃省职业院校技能大赛-网络构建-试卷
【题目】【网络系统管理】2022年甘肃省职业院校技能大赛-网络构建-试卷
【题目】【网络系统管理】2022年甘肃省职业院校技能大赛-网络构建-试卷
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套A模块
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套A模块
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套A模块
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套B模块-1
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套B模块
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套B模块-1
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套B模块-2
【题目】2023年全国职业院校技能大赛 GZ073 网络系统管理赛项赛题第3套B模块
2023年江西省赣州市技能大赛 网络安全竞赛试题任务书
2023年江西省赣州市技能大赛 网络安全竞赛试题任务书
192 0
【Sword系列】第七届全国残疾人职业技能大赛样题-网络安全-疑惑的汉字
ROT13(回转13位,rotate by 13 places,有时中间加了个连字符称作ROT-13)是一种简易的替换式密码。ROT13被描述成“杂志字谜上下颠倒解答的Usenet点对点体”。ROT13 也是过去在古罗马开发的凯撒加密的一种变体。
149 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等