讨论/题目交流/LCP 3. 机器人大冒险 疑问求解/
LCP 3. 机器人大冒险 疑问求解

简介

  • 求助,为什么这么写不对呢?
  • 是在判断障碍物和终点的前后方面出错了吗?
  • 完全想不通。
  • 以下是代码和出现错误的用例
  • 如果有注释或者代码命名或者任何可以改进的地方也请告诉我,谢谢你
46 / 53 个通过测试用例
"URR"
[[4, 2]]
3
2
输出:false
预期:true
class Solution {
    public boolean robot(String command, int[][] obstacles, int x, int y) {
        char[] s=command.toCharArray();
        int x_AllForOneRound=0,y_AllForOneRound=0,round=0;//x_AllForOneRound为一个周期,x轴上的总步数,y_AllForOneRound为一个周期,y轴上的总步数
        int i=0,j=0,x_new=0,y_new=0,step=0;
        for(i=0;i<s.length;i++)//首先,计算一个周期内的x、y总步数
        {
            if(s[i]=='U')
            {
                y_AllForOneRound++;
            }
            if(s[i]=='R')
            {
                x_AllForOneRound++;
            }
        }
        round=((x/x_AllForOneRound)<=(y/y_AllForOneRound))?(x/x_AllForOneRound):(y/y_AllForOneRound);//计算终点在第几圈,以圈数中的较小值为准,round=0就是第一圈,round=1就是第二圈,以此类推。
/*以2X3的方格为例(x=2,y=3),假设该方格为第二个循环(round=1),即左下角坐标为(2,3)。
                        
                        -----------------(4,6)
                        :(2,6)  :       |
                        :       :       |
                        ---------————(4,5)
                        :       |       :
                        :       |       :
                        ————---------
                        |       :       :
                        |(2,3)  :       :
        ---------------------------------
        :       :       |
        :       :       |
        ---------————
        :       |       :
        :       |       :
        ————---------
        |       :       :
        |       :       :
   (0,0)-----------------
    用右上角点(4,6),分别用x_AllForOneRound和y_AllForOneRound(x一个周期内的总步数,y一个周期内的总步数)来计算圈数,为(4/2=2,6/3=2),即用x算是第三圈(round=2),用y算是第三圈(round=2)。
    用右侧边上的点计算圈数为(2,1),上侧边上的点计算圈数为(1,2),此外所有点(包括内部点,左边,下边),计算圈数都为(1,1)。
    由此可知,判断圈数时,只用x或者y都是不完整的,可能导致圈数不同,还有因为重复点而导致的圈数计算错误(因为右上角又算第二圈也算第三圈)。下面此处的说明如下:如果是(2,3)点,归作第0圈,如果是(4,6)点归作第1圈,又因为对每圈的起始点就进行判断,所以完全覆盖了对所有点的判断,没有遗漏。*/

    //以下的代码是判断能否到达预定的终点,即“会不会出现设置的终点根本不在路径上”的问题
       
       if(round*x_AllForOneRound<=x&&x<=(round+1)*x_AllForOneRound&&round*y_AllForOneRound<=y&&y<=(round+1)*y_AllForOneRound){//用计算得到的圈数验证“是否终点的xy坐标都在同一个周期内,通俗讲就是同一个周期方框内”
    //如果在周期上的话,验证是不是真的位于路径上
            x_new=0;//记录一个周期内x方向上走过的步数
            y_new=0;//记录一个周期内y方向上走过的步数
            for(step=0;step<s.length;step++)//根据指令列,一步步走
                {
                    if((round*x_AllForOneRound+x_new)==x&&(round*y_AllForOneRound+y_new)==y){//每走一步判断一次是否到达终点
                        break;//如果能到达,再进行下面的障碍物判断
                    }
                    if(s[step]=='U')
                    {
                        y_new++;
                    }
                    if(s[step]=='R')
                    {
                        x_new++;
                    } 
                }
        
        }else{
            return false;//否则,根本不在路径上,直接返回不可到达
        }
//通过了以上验证的实例,都是终点位于路径上的,所以很多案例都无须下面的代码就退出了

        if(obstacles.length==0){//如果没有障碍物,终点又在路径上,直接说明可到终点,结束
        return true;
        }
//通过上一小段代码,“终点在路径上,而且根本没有障碍物”的案例也全都筛去了

//接下来才对又能到达终点又有障碍物的案例进行分析
        for(j=0;j<obstacles.length;j++){//对障碍物一个个判断是否在路径上,因为障碍物比较少,比对圈数循环要快
        round=((obstacles[j][0]/x_AllForOneRound)<(obstacles[j][1]/y_AllForOneRound))?(obstacles[j][0]/x_AllForOneRound):(obstacles[j][1]/y_AllForOneRound);//还是以算出的圈数较小值为准,这一大句简化一下其实就是a<b?a:b的句式,求较小值

//注意以下,为了实现到达终点后,再有障碍物也不会影响结果的目的,把右上角的重复点都归进前一圈中,这样比较好统一判断
        if(obstacles[j][0]/x_AllForOneRound==obstacles[j][0]/y_AllForOneRound)
            {
                round=(obstacles[j][0]-1)/x_AllForOneRound;
            }
        //判断障碍物是否在周期方框内,因为有(3,100)、(200,3)这样的障碍物,根本不在周期内,完全不用管
        if(round*x_AllForOneRound<=obstacles[j][0]&&obstacles[j][0]<=(round+1)*x_AllForOneRound&&round*y_AllForOneRound<=obstacles[j][1]&&obstacles[j][1]<=(round+1)*y_AllForOneRound){
            x_new=0;
            y_new=0;    
            for(step=0;step<s.length;step++)//还是走一步,判断一步
            {
                if((round*x_AllForOneRound+x_new)==x&&(round*y_AllForOneRound+y_new)==y){
                    return true;//如果已经到了终点,直接返回可到达,先于障碍物退出所以再有障碍物也不会影响结果,又或者障碍物和终点在同一点也会先判断为到了终点
                }
                if((round*x_AllForOneRound+x_new)==obstacles[j][0]&&(round*y_AllForOneRound+y_new)==obstacles[j][1]){
                    return false;//如果碰到障碍物,直接返回不可到达,已经到达以后,再遇到障碍物也无效
                }             
                if(s[step]=='U')
                {
                    y_new++;
                }
                if(s[step]=='R')
                {
                    x_new++;
                }            
            }
            }
        }

//以下是已经通过了的一个笨办法,上面的代码是改进
        /*
        for(i=0;i<=round;i++)//一圈圈判断
        {
            if(obstacles.length==0){//如果没有障碍物,直接说明可到终点
                return true;
            }
            for(j=0;j<obstacles.length;j++){
                if(i*x_AllForOneRound<=obstacles[j][0]&&obstacles[j][0]<=(i+1)*x_AllForOneRound&&i*y_AllForOneRound<=obstacles[j][1]&&obstacles[j][1]<=(i+1)*y_AllForOneRound)//如果在某一周期内有障碍物,判断障碍物是否在路上
            {
                x_new=0;
                y_new=0;
                for(step=0;step<s.length;step++)
                {
                    
                    if(s[step]=='U')
                    {
                        y_new++;
                    }
                    if(s[step]=='R')
                    {
                        x_new++;
                    }
                    if((i*x_AllForOneRound+x_new)==x&&(i*y_AllForOneRound+y_new)==y){
                        return true;//如果已经到了终点,直接返回可到达
                    }
                    if((i*x_AllForOneRound+x_new)==obstacles[j][0]&&(i*y_AllForOneRound+y_new)==obstacles[j][1]){
                        return false;//如果碰到障碍物,直接返回不可到达,已经到达以后,再遇到障碍物也无效
                    }
                }
            }
            }
        }*/
        return true;
    }
}
展开讨论
溪鸢发起于 2020-02-21
最近编辑于 2020-02-21
共 1 个讨论

考虑的太复杂了,感觉没人有耐心看完。
力扣这个平台给了错误的用例,其实出了问题都可以本地 Debug 单步出来。
懒得装相应的 ide 处理,就大致分析了一下:
首先就是分析样例,终点在第二个周期内,且障碍物在终点之后,正常来讲你的代码肯定会返回 true ,但是实际上返回了 false ,那么问题只会出现在两部分:

  • 判断终点是否在路径上这部分
  • 判断障碍是否在路径上这部分

考虑到有能够通过的样例,所以合理猜测错误的地方在判断障碍是否在路径上。
而且当前障碍在终点之后,顺着注释找到对应的代码:

//注意以下,为了实现到达终点后,再有障碍物也不会影响结果的目的,把右上角的重复点都归进前一圈中,这样比较好统一判断
        if(obstacles[j][0]/x_AllForOneRound==obstacles[j][0]/y_AllForOneRound)
            {
                round=(obstacles[j][0]-1)/x_AllForOneRound;
            }

然后就能看到判断语句后边的条件(obstacles[j][0]/y_AllForOneRound)写错了,应该为:(obstacles[j][1]/y_AllForOneRound)。
其余部分没看,不知道是否还有其他问题。
另外:到达终点后的障碍很容易就可以判断出来:只要横纵坐标有一个大于终点的横纵坐标就一定在终点之后,完全不用考虑,直接 continue 就好。
最好还是看看题解部分各位大佬的解答