题目:

力扣团队买了一个可编程机器人,机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command,机器人就会无限循环这条指令的步骤进行移动。指令有两种:

U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。
不幸的是,在 xy 平面上还有一些障碍物,他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。

给定终点坐标(x, y),返回机器人能否完好地到达终点。如果能,返回true;否则返回false。

示例 1:

输入:command = “URR”, obstacles = [], x = 3, y = 2
输出:true
解释:U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。

思路:

将一次循环后的所有位置嵌入数组
然后通过 helper 函数判断能否到达终点
达到终点前是否会碰到障碍物。
判断逻辑是 是否 有位置减去数组中的值的余数为零,且倍率相等。
是则证明在路径上。
是则返回 true
主函数根据情况进行处理。

class Solution {
    public static boolean robot(String command, int[][] obstacles, int x, int y) {
        int len = command.length();
        int[][] dp = new int[len][2];
        int xStep = 0,yStep = 0;
        for(int i=0;i<len;i++){
            char c = command.charAt(i);
            if(c=='R') xStep++;
            if(c=='U') yStep++;
            dp[i][0] = xStep;
            dp[i][1] = yStep;
        }
        if(!helper(dp,x,y,xStep,yStep)){

            return false;
        }
        for(int[] data:obstacles){
            if(data[0]>=x&&data[1]>=y)
                continue;
            if(helper(dp,data[0],data[1],xStep,yStep)){

                return false;
            }
        }
        return true;
    }

    public static boolean helper(int[][] dp, int x, int y, int xStep, int yStep) {
        for(int[] tmp:dp){

            if((x-tmp[0])%xStep==0&&(y-tmp[1])%yStep==0&&(x-tmp[0])/xStep==(y-tmp[1])/yStep){

                return true;
            }
        }
        return false;
    }

}
Logo

DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐