google 扫地机器人

class robot{
   
    int[] pos;
    Set<String> visited;
    Stack<int[]> stack;
    Stack<Integer> actions;

    robot(){
        pos = new int[]{0, 0};
        visited = new HashSet<>();
        stack = new Stack<>();
        stack.push(new int[]{0,0,0});
        actions = new Stack<>();
    }

    private boolean move(){}

    private void turnLeft(){}

    private void turnRight(){}

    private boolean moveF(){
        boolean succ = move();
        if(succ)
            pos[1]++;
        return succ;
    }

    private boolean moveL(){
        turnLeft(1);
        boolean succ = move();
        if(succ)
            pos[0]--;
        turnRight(1);
        return succ;
    }

    private boolean moveR(){
        turnRight(1);
        boolean succ = move();
        if(succ)
            pos[0]++;
        turnLeft(1);
        return succ;
    }

    private boolean moveB(){
        turnLeft(2);
        boolean succ = move();
        if(succ)
            pos[1]--;
        turnRight(2);
        return succ;
    }

    private boolean moveNext(int x){
        if(x == 0) return moveF();
        else if(x == 1) return moveR();
        else if(x == 2) return moveB();
        else if(x == 3) return moveL();
        return false;
    }

    private void Return(int x){
        if(x == 0) moveB();
        else if(x == 1) moveL();
        else if(x == 2) moveF();
        else if(x == 3) moveR();
    }


    private void clean(){}

    private void traverse(){
        while(!stack.isEmpty()){
            int[] cur = stack.peek();
            int x = cur[0], y = cur[1];
. 1point3acres.com             
            if(!visited(posStr(cur[0], cur[1]))){
                visited.add(posStr(cur[0], cur[1]));
                clean();
            }

            String[] nextPoint = new String[]{posStr(cur[0], cur[1]+1),posStr(cur[0]+1, cur[1]),
                        posStr(cur[0], cur[1]-1),posStr(cur[0]-1, cur[1])};

            while(cur[2] < 4 && (visited.contains(nextPoint(cur[2])) || !moveNext(cur[2])))
                cur[2]++;

            if(cur[2] == 4){
                stack.pop();
                while(!stack.isEmpty() && !(pos[0] == stack.peek()[0] && pos[1] == stack.peek()[1])){
                    Return(actions.pop());
                }
            }else{
                cur[2]++;
                stack.push(new int[]{pos[0], pos[1], 0});
            }
        }
    }
}

递归比这个简单

我面试面了这道题最后过了。我是dfs，用一个set记录visited。设定起点是原点，dfs helper函数要传机器人当前方向，用0123表示就可以。每一个helper函数用for循环走四次。每一次按照顺时针或者逆时针转一下。把走过的坐标和cannot move的点都放进visited。最重要的是走完发现无路可走之后要再转向后方走一步再转向后，也就是返回上级helper函数时机器人所在的位置和面朝的方向。

我面试的时候小哥说我是他面过的第一个把这道题题和followup都做完的candidate。难点在于一是包了api进去要手动控制方向，二是要参数具体化这个房间。

siy 发表于 2018-3-9 09:24
我面试面了这道题最后过了。我是dfs，用一个set记录visited。设定起点是原点，dfs helper函数要传机器人当 ...

谢谢分享。能不能分享一下代码呢？我来研究研究，多谢！

这题需要注意的点 楼里有人已经说得很详细了 就是dfs+自己定义一种方式hash已经走过的格子+手动在递归函数结束时调整机器人的方向的位置

重点就是自己写一遍 然后跑test case  光看别人的代码 很容易忽略里面的细节

我记得难点就是递归的时候方向转换的问题

siy 发表于 2018-3-9 09:28
我面试的时候小哥说我是他面过的第一个把这道题题和followup都做完的candidate。难点在于一是包了api进去要 ...

嗯嗯 谢谢你贡献思路 我自己写过一次 我的思路就是每次递归结束后保证返回上一个格子并且方向也保持一致 可惜面试没有看到

siy 发表于 2018-3-9 09:24
我面试面了这道题最后过了。我是dfs，用一个set记录visited。设定起点是原点，dfs helper函数要传机器人当 ...

差不多是这个意思？

void dfs(x, y, back_direction) {
    if(visited(x, y))
        return;

    visited.add(x,y);
   
    if(move(UP))        dfs(x, y - 1, DOWN);
    if(move(LEFT))     dfs(x - 1, y, RIGHT);
    if(move(DOWN))   dfs(x, y + 1, UP);
    if(move(RIGHT))   dfs(x + 1, y, LEFT);

    move(back_direction);
}

rhwfyf 发表于 2018-3-10 01:09
差不多是这个意思？

void dfs(x, y, back_direction) {

差不多。但是api给的是顺时针转逆时针转。所以四个if里面应该是转0次1次2次3次。然后cannot move的点是房间边界或者障碍物。也要加进visited