Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

LeetCode LCP 3 机器人大冒险

乌克兰大野猪 2019-10-02 09:42:00 阅读数:14 评论数:0 点赞数:0 收藏数:0

题目解析:

对于本题主要的核心是对于一个指令字符串如“RURUU”,如果我们假设它的终点坐标为(8,8),其实只要统计指令字符串中的R的个数和U的个数(对于我给出的例子而言,num_R == 2,num_U == 3),显然不管我们是否能到达终点,这条指令至少要走不止一遍才有可能,那么我们只要将它在达到终点前必走的x轮减去(对于我给出的例子而言x == min(8 / 2 ,8 / 3)== 2,则忽略中间走的轮数,就能把终点的位置转化为(4,2)),则就能求出最后那不足一轮的情况下需要U多少个,R多少个才能到达终点,然后遍历指令字符串,一步一步模拟即可,一旦超过终点的x或者y则永远不可能到达,对于障碍点来说也是一样,把它们当作目标点来求能否到达即可,这个判断的过程可以单独写作一个函数更为方便。解题时,我们先判断障碍点(x <= 终点x,y <= 终点y,否则根据题意,该障碍点无效)能否到达,在所有有必要判断的障碍点都不会碰到后再判断终点能否到达

本题代码:

 class Solution {
 public:
     int min(int x, int y){
         return x < y ? x : y;
     }
     bool judge(string command, int x_num, int y_num, int x, int y){
         int temp = min(x/x_num, y/y_num);       //temp记录最小公倍数
         x = x - x_num*temp;      //x记录的是R
         y = y - y_num*temp;      //y记录的是U
         //此时的x和y代表终点相对于第一次循环的位置
         if(x ==  && y == ) return true;
         else{
             int len_cmd = command.size();
             for(int i = ; i < len_cmd; i++){
                 if(command[i] == 'U'){
                     y--;
                     if(y < ) return false;
                 }else{
                     x--;
                     if(x < ) return false;
                 }
                 if(x ==  && y == ) return true;
             }
         }
         return true;
     }
     bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
         int len_cmd = command.size();
         int x_1 = ;
         int y_1 = ;
         //统计第一轮循环能走到的地方
         for(int i = ; i < len_cmd; i++){
             if(command[i] == 'R'){
                 x_1++;
             }else{
                 y_1++;
             }
         }
         //把每一个障碍点(该障碍点的x和y都要小于终点的x和y)当做是终点求能否到达 能到达则return false
         int len_obs = obstacles.size();
         for(int i = ; i < len_obs; i++){
             if(obstacles[i][] <= x && obstacles[i][] <= y){
                 //能到达则return false
                 if(judge(command, x_1, y_1, obstacles[i][], obstacles[i][]) == true) return false;
             }
         }
         //如果所有的终点之内的障碍点都不会到达 则直接判断终点是否可以到达
         if(judge(command, x_1, y_1, x, y) == true) return true;
         else return false;
     }
 };

 

版权声明
本文为[乌克兰大野猪]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/findview/p/11616836.html