LeetCode LCP 3 机器人大冒险

题目解析：

对于本题主要的核心是对于一个指令字符串如“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;

     }

 };

巴特西

LeetCode LCP 3 机器人大冒险

题目解析：

本题代码：

最新文章

热门文章