google 扫地机器人

TsengJuiWang 发表于 2018-4-7 12:42
我记得turnLeft（k）是90*K

是的，轉K次其實就代表轉90*K度

lf963 发表于 2018-4-7 14:21
你是正確的！是我搞錯了。下面是我的想法

感觉不用else，这样就行了？

1.                 if(Move()) {
   
2.                     DFS(myRobot,x + directions[faceTo][0], y + directions[faceTo][1], visited, faceTo);
   
3.                 }
   
4.                 visited.add(new Coordinate(x + directions[faceTo][0], y + directions[faceTo][1]));
   
5.                 moveBack();

复制代码

lf963 发表于 2018-4-7 14:21
你是正確的！是我搞錯了。下面是我的想法

不知道我理解的对不对，else意味着前方是障碍物，robot还在current cell里，所以是不需要moveback的，直接进入下一个for就可以了。所以是不是只有在if里，dfs结束之后才需要moveback？

misty1007 发表于 2018-4-9 23:50
不知道我理解的对不对，else意味着前方是障碍物，robot还在current cell里，所以是不需要moveback的，直 ...

對！你是正確的！　moveback應該放在 if 裡面，請問可以修改文章嗎？我想把我之前寫的修改一下

wtcupup 发表于 2018-4-9 02:06
感觉不用else，这样就行了？

其實也可以！這樣簡潔多了

lf963 发表于 2018-4-7 14:21
你是正確的！是我搞錯了。下面是我的想法

楼主你好。关于你的这个解法我觉得还有一些地方值得商量。

1. 关于 28 - 33 行， 33 行moveBack（）调用的时候，要确保机器人的此时的方向 和进入29 行DFS 之前的方向一致，这样 moveBack里 掉头- 再掉头才是正确的。但目前来看，可能你这样写有点问题。我们假设 for loop 里的 moveback 都可以顺利的完成，那么此时 direction 应该是进入递归时 （14行） 的 direction + 3。那么当退出13- 33 行的 整个DFS 回到 father 级别的 DFS 循环时，此时应该是在 father 循环的 30 行，但此时的方向并非是 进入 29 行时的方向，而是该方向 + 3。 这样调用 moveback 会回到方向 + 1的位置，而非 方向 + 2的位置。

2. 另外关于在 程序里用 turnleft / right 搭配方向，我觉得既然direction 变量就是被我们用了控制方向的，那么何不把 turnLeft / right 包装在 changeDirection里，一来方便管理，而来不用同时照顾 direction变量和 turnleft 操作

3. 我感觉整个题目的意思就是用 changeDirection 和 moveback 来模拟 函数的 return 语句，也就是说在DFS里任何 return的地方 都用 changeDirectionToBeginningDirection + moveback 一次。因此直接 在 DFS 的return 位置 调用 moveback 就可以了。

以下是我写的代码
package googl;

/**
* Created by Administrator on 4/19/2018.
* 0. 无论如何都需要有 direction， 顺时针 0 - 1 - 2 - 3， 增加为每次 turnRight，
* 1.机器人改变 direction 实际上对应的是 若干个 turnleft / turnRight, 所以 要有个一个 changeToDirection(int from, int to), 里面包若干个 turnleft/ turnRight
* 2.函数 return 时，机器人要 return回上一个点 -- > 沿进入该点的方向 之反方向 preDir -- preDir + 2， （或两次 turnright） 走一个 move,并返回到 进入改点的方向， 比如保持return的时候 其方向和原来的方向一致 同时回到原来的方向
* 3.本版本 是机器人内部保存  direction. x, y position 版本，默认 0 - direction为放置 机器人时 的初始 direction，房间可以颠倒过来看，怎样
*/
public class IRobot_9001 {
    Robot robot;
    int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int direction;
    /*不必保留 当前 posX， posY的位置，位置信息只在检查下一点是否可行时有用，DFS 中带入即可*/

    public void sweep(int[][] map, int[] start) {
        this.robot = new Robot();
        boolean[][] visited = new boolean[map.length + 1][map[0].length + 1];
        dfs(start[0], start[1], visited);
    }

    public void changeDirectionTo(int direction) {
        /*clockwise turn -- > direction increases*/
        if (direction == this.direction) return; // 不用改
        int delta = direction - this.direction > 0 ? direction - this.direction : direction - this.direction + 4;
        for (int i = 0; i < delta; i++) {
            robot.turnRight();
        }
. Χ        this.direction = direction;
    }

    public void moveBack() {
        changeDirectionTo(this.direction + 2);
        robot.move();
        changeDirectionTo(this.direction + 2);
    }

    public void dfs(int x, int y, boolean[][] visited) {
        robot.clean(); // 成功进入 x,y 扫地
        /*首先保存原有方向，便于退出时恢复*/
        int prevDirection = this.direction;
        /*有四个方向可选，当前方向继续 + 向右转 1， 2， 3 次
        * 其中向右转2次相当于回退，由于 visited 必然标记为访问过，则必定不成功*/
        /*下一步未访问过，且下一步访问成功*/
        for (int i = 0; i < 4; i++) {
            int nextX = x + dirs[i][0];
            int nextY = y + dirs[i][1];
            changeDirectionTo(this.direction + 1); // 转向
            if (!visited[nextX][nextY]) {
                visited[nextX][nextY] = true;
                /*不可移动的就跳下一轮循环*/
                if (robot.move()) {
                    /*可以挪到下一个，在下一个继续 DFS, 注意此时进入下一层 DFS 的是新的 direction*/
                    dfs(nextX, nextY, visited);
                }
            }
        }
        changeDirectionTo(prevDirection); // 重要，恢复成原来进入该格子时候的 方向，再做 moveback
        moveBack(); // moveback里 两次转向保证了退回上一格仍然是进入该格子的方向
    }
}

class Robot {
    boolean move() {
        /*Default method by moving one step on the current direction
        * will return true if move successfully*/
        return true;
    }
    void turnLeft() {
        /*change direction to +90*/
    }

    void turnRight() {
        /*change direction to -90*/
    }
    void clean() {
        /*Do clean*/
    }
}

1. function cleanRoom(robot) {
   
2.   const seen = new Set();
   
3.   const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
   
4.   dfs(0, 0, 0);
   
5.   
   
6.   function dfs(dir, r, c) {
   
7.     robot.clean();
   
8.     seen.add(r+':'+c);
   
9.     for (let i = 0; i < 4; i++) {
   
10.       const [dr, dc] = dirs[(dir+i)%4];
    
11.       const rr = r+dr;
    
12.       const cc = c+dc;
    
13.       
    
14.       if (seen.has(rr+':'+cc) || !robot.move()) {
    
15.         robot.turnRight();
    
16.       } else {
    
17.         dfs((dir+i)%4, rr, cc);
    
18.         robot.turnLeft();
    
19.       }
    
20.     }
    
21.     robot.turnRight();
    
22.     robot.turnRight();
    
23.     robot.move();
    
24.   }
    
25. }

复制代码

补充内容 (2018-7-22 09:23):
https://leetcode.com/problems/robot-room-cleaner/description/
https://leetcode.com/problems/robot-room-cleaner/discuss/152262/Concise-JavaScript-solution-(25-lines)

感谢！！！

lc有原题 自己看discuss