Leetcode 模拟行走机器人

机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：

    -2：向左转 90 度
    -1：向右转 90 度
    1 <= x <= 9：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物。

第 i 个障碍物位于网格点  (obstacles[i][0], obstacles[i][1])

如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。

返回从原点到机器人的最大欧式距离的平方。

示例 1：

输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)

示例 2：

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处

提示：

    0 <= commands.length <= 10000
    0 <= obstacles.length <= 10000
    -30000 <= obstacle[i][0] <= 30000
    -30000 <= obstacle[i][1] <= 30000
    答案保证小于 2 ^ 31

链接：https://leetcode-cn.com/problems/walking-robot-simulation
 

思路：这道题做了半天，看了官方的题解，用了set容器，但是c语言里面没有这个东东，于是尝试了一种新思路，没想到过了。

这道题如果暴力遍历obstacles，会超时，于是想着对obstacles进行排序，但是如何对二位数组排序呢，我的思路是将二维转化为一维数组，排序后，用二分搜索遍历obstacles。遍历时间复杂度O(logn)。

int turn(int d, int cmd) {int ret = d;switch(d) {case 0:if(cmd == -1) ret = 1; else ret = 3; break;case 1:if(cmd == -1) ret = 2; else ret = 0; break;case 2:if(cmd == -1) ret = 3; else ret = 1; break;case 3:if(cmd == -1) ret = 0; else ret = 2; break;default:break;}return ret;
}bool judge(int x, int y, int** o, int os){int i;int r = x + y * 30000;int left = 0, mid = os / 2, right = os;if(!os || r > o[os-1][0] || r < o[0][0])return true;if(r == o[mid][0])return false;while(left + 1 < right) {if(r > o[mid][0]) {left = mid;mid = (left + right) / 2;} else if (r < o[mid][0]){right = mid;mid = (left + right) / 2;} else {return false;}}return true;
}int cmp(void *a, void *b) {return (*(int **)a)[0] - (*(int **)b)[0];
}int robotSim(int* commands, int commandsSize, int** obstacles, int obstaclesSize, int* obstaclesColSize){int x = 0, y = 0;int d = 0;int ret = 0;char b[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};int i;for(i = 0; i < obstaclesSize; i++)obstacles[i][0] = obstacles[i][0] + obstacles[i][1] * 30000;qsort(obstacles, obstaclesSize, sizeof(int *), cmp);for(i = 0; i < commandsSize; i++) {switch(commands[i]) {case -1:case -2:d = turn(d, commands[i]);break;default:while(commands[i]--) {if (judge(x+b[d][0], y+b[d][1], obstacles,obstaclesSize)) {x += b[d][0];y += b[d][1];} elsebreak;}break;}ret = ret < x * x + y * y ?  x * x + y * y : ret;}return ret;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！