robot moving on the surface of a square

╰半橙微兮° 2021-11-24 01:12 309阅读 0赞

题目

机器人在形状为green house立方体的5个表面移动进行打扫，初始位置为表面1上的某个给定位置，输入一串由123组成的连续指令（1：向前移动1个单位；2：右转方向；3：左转方向）操作机器人，判断最后机器人所处表面(1/2/3/4/5)。

1126979-20190522232414798-1654376216.png

细节

1) 当移动到当前表面边界时执行前移操作(op=1)时会这样移动到对应毗邻的表面：

1126979-20190522233827123-1218850384.png 好难画啊口区

2) 机器人位于表面1、2、3、4的底层边缘时试图往下移动的操作将会失败，位置不变。

i.e.

输入：N（int，立方体棱长）、location_r(int，初始位置竖直坐标）、loation_c(int，初始位置水平坐标）、 ops（int[200]，由1/2/3组成的指令串）；

输出：执行完所有指令后机器人所在的表面编号。

例子：N=4，初始位置为3，2（注意题目的输入以1为起点），输入长度25的指令1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1。

轨迹：

1126979-20190523154741184-1298771793.png

好丑啊救命

思路

[1] 把立方体表面展开并设定绝对方向；

绝对方向: 展开后的二维空间上的方向，只有上下左右4个。counterpart应该不能叫相对方向吧，反正是三维空间中根据当前所在具体平面+平面上的方向所确定的∈R3的向量吧阿没关系啦反正这个跟解题应该没什么关系

e.g. N=4，展开立方体并以表面1方向为基准，每个表面以左上角为坐标原点。//也可以按别的方式展开 看个人偏好

1126979-20190523091745721-1676459926.png

[2] 用4个int变量grid, location_r, location_c, direction追踪机器人每执行完一个指令后的状态。

  1.     grid:  机器人当前所在表面编号
  3.     location\_r: 机器人当前所在行坐标 //我个人是以0为起始的 
  5.     location\_c: 机器人当前所在列坐标
  7.     direction: 机器人当前朝向 //这里关联前面提到的绝对方向

[3] 指令处理：可分为 向前移动机器人 和 转动方向

[3-1] 转动方向

当op为2或3的时候相应的顺时针/逆时针改变方向 e.g. 当前方向为up时，收到指令3，逆时针转动90度所以方向更新为left。

实现的时候可以考虑用4个整形常量0 1 2 3标记上下左右 或者逆时针 上左下右 或者顺时针 上右下左 随便啦反正后面不要突然弄混就是了 但我觉得这样做可读性不是很强，我个人偏向用枚举enum directions{up, left, down, right}虽然考试系统的编译器比较垃圾不认识enum所以我最后又只能默默改回用整数罢了

[3-2] 向前移动机器人

只要看当前的绝对方向是什么再对坐标做相应的更新（先不管可能会遇到坐标越界需要更换所在表面的问题），e.g.direction为up时坐标r轴+=-1 c轴+=0

实现建议 上如果先前是用简单的连续整数标记4个方向比如0/1/2/3分别表示up/left/down/right那么可以用一个4*2的二维数组存储坐标更新的可能delta值：deltas[4][2]={ {0, -1}, {-1, 0}, {1, 0}, {0, 1}}，这样就可以直接用方向值作为下表获取坐标更新的delta值直接递增在原坐标上计算

当然如果题目想要再复杂一点可能一次不是只移动一格那么deltas里的值也可以改不过我也不想考虑这么无聊的情况了hehe

e.g.

  1. enum directions {up, left, down, right};
  2. int deltas[4][2]={
  3.     {
  4.     0, -1}, {-1, 0}, {
  5.     1, 0}, {
  6.     0, 1}};
  7. //operates, change direction or move or whatever
  8. ...
  9. //get an op==1 indicates that you need to move forward
  10. location_r+=deltas[direction][0];
  11. location_c+=deltas[direction][1];

如果更新后的坐标值是合法的 i.e. 在0和N-1之间 （当然如果是从1起始就是在1和N之间啊我为什么要打这些废话）那就完了

如果更新后的坐标值不合法说明它可能要移动到另一个平面 或者 试图移动到最底下那个不能到达的平面但没有成功，那就要对坐标值进行再次更新使它合法，有时候方向也要根据情况进行更新。

[3-2-2] 合法化非法坐标 //听起来为什么这么诡异

根据之前的展开图找规律进行相应变更

1126979-20190523100439824-1243363.png

e.g. 当在表面5时location_c<0时，说明机器人实际上已经移动到表面4的上侧，对应的规律就是r变为0【因为反正题目中只移动一步所以确定是在表面4的第一行】而c变为原本的r值。direction也会从原来的left变为down。 其他情况以此类推。

当在与底面毗邻的表面1/2/3/4试图往底面移动时(e.g. grid==2, location_r<0)时会失败，把当前非法的坐标值更新为边界值，方向不变。

[4] 最后返回当前记录的grid值

关于grid location和directon的追踪

实现全部在main里写也是没问题，但是我比较喜欢分成几个函数来写。这样的话为了保证函数中做的变更能更新到main里的表面/坐标/方向的变量值就需要把它们按引用传递而不是按值传递， C/C++可以把参数设为引用或者指针，java的话好像基本数据类型参数是默认按值传递的，但好像也有个什么途径可以把它们封装成对象就能按引用传递了。

如果你们直接把它们用作返回值当我没说

用全局变量也可以啦但我不是很喜欢

总体

  1. int grid = 1, location_r, location_c, direction;
  3. void robot_move(int& location_r, int& location_c, int& direction);
  4. bool locationInvalid(const int location_r, const int location_c, const int N);
  5. void robot_rectify(int& grid, int& location_r, int& location_c, int& direction, const int N);
  6. void changeDirection(int& direction, const int op);
  8. //依此执行输入指令
  9. for (int op : ops) {
  10.     switch (op) {
  11.         case 1: //move forward
  12.             robot_move(location_r, location_c, direction); //update location
  13.             if (locationInvalid(location_r, location_c, N))
  14.                 robot_rectify(grid, location_r, location_c, direction, N); //rectify the illegal location values and udpate direction perhaps
  15.             break;
  16.         case 2:
  17.         case 3:
  18.             changeDirection(direction, op);
  19.             break;
  20.     }
  21. }

完整代码：

  1. #include <iostream>
  2. using namespace std;
  4. enum directions { up, left, down, right };
  5. int deltas[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
  8. void robot_move(int& location_r, int& location_c, int& direction) {
  9.     //increment locations with specific delta according to the current direction
  10.     location_r += deltas[direction][0];
  11.     location_c += deltas[direction][1];
  12. }
  14. bool locationInvalid(const int location_r, const int location_c, const int N) {
  15.     return location_r < 0|| location_r >= N || location_c < 0 || location_c >= N;
  16. }
  18. void robot_rectify(int& grid, int& location_r, int& location_c, int& direction, const int N) {
  19.     switch (grid) {
  20.         case 1:
  21.             if (location_r < 0) {
  22.                 grid = 5;
  23.                 location_r = N - 1;
  24.             }
  25.             else if (location_r >= N) {
  26.                 location_r = N - 1;
  27.             }
  28.             else if (location_c < 0) {
  29.                 grid = 4;
  30.                 location_c = N - 1;
  31.             }
  32.             else if (location_c >= N) {
  33.                 grid = 3;
  34.                 location_c = 0;
  35.             }
  36.             break;
  37.         case 2:
  38.             if (location_r < 0) {
  39.                 location_r = 0;
  40.             }
  41.             else if (location_r >= N) {
  42.                 grid = 5;
  43.                 location_r = 0;
  44.             }
  45.             else if (location_c < 0) {
  46.                 grid = 4;
  47.                 direction = directions::right;
  48.                 location_r = N - 1 - location_r;
  49.                 location_c = 0;
  50.             }
  51.             else if (location_c >= N) {
  52.                 grid = 3;
  53.                 direction = directions::left;
  54.                 location_r = N - 1 - location_r;
  55.                 location_c = N - 1;
  56.             }
  57.             break;
  58.         case 3:
  59.             if (location_r < 0) {
  60.                 grid = 5;
  61.                 direction = directions::left;
  62.                 location_r = N-1-location_c;
  63.                 location_c = N - 1;
  64.             }
  65.             else if (location_r >= N) {
  66.                 location_r = N - 1;
  67.             }
  68.             else if (location_c < 0) {
  69.                 grid = 1;
  70.                 location_c = N - 1;
  71.             }
  72.             else if (location_c >= N) {
  73.                 grid = 2;
  74.                 direction = directions::right;
  75.                 location_r = N - 1 - location_r;
  76.                 location_c = N - 1;
  77.             }
  78.             break;
  79.         case 4:
  80.             if (location_r < 0) {
  81.                 grid = 5;
  82.                 direction = directions::right;
  83.                 location_r = location_c;
  84.                 location_c = 0;
  85.             }
  86.             else if (location_r >= N) {
  87.                 location_r = N - 1;
  88.             }
  89.             else if (location_c < 0) {
  90.                 grid = 2;
  91.                 direction = directions::right;
  92.                 location_r = N - 1 - location_r;
  93.                 location_c = 0;
  94.             }
  95.             else if (location_c >= N) {
  96.                 grid = 1;
  97.                 location_c = 0;
  98.             }
  99.             break;
  100.         case 5:
  101.             if (location_r < 0) {
  102.                 grid = 2;
  103.                 location_r = N - 1;
  104.             }
  105.             else if (location_r >= N) {
  106.                 grid = 1;
  107.                 location_r = 0;
  108.             }
  109.             else if (location_c < 0) {
  110.                 grid = 4;
  111.                 direction = directions::down;
  112.                 location_c = location_r;
  113.                 location_r = 0;
  114.             }
  115.             else if (location_c >= N) {
  116.                 grid = 3;
  117.                 direction = directions::down;
  118.                 location_c = N-1-location_r;
  119.                 location_r = 0;
  120.             }
  121.             break;
  122.     }
  124. }
  125. void changeDirection(int& direction, const int op) {
  126.     switch (op) {
  127.         case 2://turn right
  128.             if (direction == directions::up)
  129.                 direction = directions::right;
  130.             else
  131.                 --direction;
  132.             break;
  133.         case 3://turn left
  134.             if (direction == directions::right)
  135.                 ++direction;
  136.             else
  137.                 ++direction;
  138.             break;
  139.     }
  140. }
  142. int main() {
  143.     //input & initialization
  145.     int N, grid, location_r, location_c, direction, k, ops[200];
  146.     cin >> N >> location_r >> location_c >> k;
  147.     --location_r;
  148.     --location_c;
  149.     for (int i = 0; i < k; i++)
  150.     cin >> ops[i];
  151.     /* test case
  152.     int N = 4, grid, location_r = 2, location_c = 1, direction, k = 25;
  153.     int ops[200] = { 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1 };
  154.     */
  155.     grid = 1;
  156.     direction = directions::up;
  157.     //依次执行输入指令
  158.     for (int i = 0; i < k; i++) {
  159.         switch (ops[i]) {
  160.         case 1: //move forward
  161.             robot_move(location_r, location_c, direction); //update location
  162.             if (locationInvalid(location_r, location_c, N))
  163.                 robot_rectify(grid, location_r, location_c, direction, N); //rectify the illegal location values and udpate direction perhaps
  164.             break;
  165.         case 2:
  166.         case 3:
  167.             changeDirection(direction, ops[i]);
  168.             break;
  169.         }
  170.     }
  171.     cout << grid << endl;
  172.     return 0;
  173. }

转载于:https://www.cnblogs.com/RDaneelOlivaw/p/10909323.html

发表评论

表情：
评论列表 （有 0 条评论，309人围观）

还没有评论，来说两句吧...

相关阅读