Google 昂赛

lidongze91 发表于 2017-11-22 15:29
空间优化，dp降维。以为2d array 里面其实每一行也是根据上一行的值生成。
所以直接1d array就可以解决 ...

大佬 求式子！

写了个扫地机器人代码，大家看看行不行？

def clean_room(robot, i, j, d, visited):
    delta = [(-1, 0), (0, 1), (1, 0), (-1, 0)]
    for k in range(4):
        new_d = (d + k) % 4
        di, dj = delta[new_d]
        if (i + di, j + dj) not in visited:
            visited.add((i + di, j + dj))
            moved = robot.move()
            if moved:
                clean_room(robot, i + di, j + dj, new_d, visited)
                # point to op dir
                robot.move()
                robot.turn_right(2)
            robot.turn_right(1)
    robot.turn_right(2)

谢谢楼主！赶快刷题去了。。。。

谢谢楼主

renou 发表于 2018-1-15 03:08
写了个扫地机器人代码，大家看看行不行？

def clean_room(robot, i, j, d, visited):

这应该是不行的  我没有理解错的话 这道题的难点就是你不知道机器人一开始的坐标 也不知道房间的地图

大概思路应该是假设机器人一开始在中间，然后你自己假设一个足够大的未探索‘’迷宫‘’ 然后用数据结构经典例题  栈走迷宫的办法(iterative) 或者是dfs(recursive) 然后使用api探索的， 边探索边更新迷宫的值

比如你假设这个房间最多50*50， 你就一开始初始化一个100*100 的char[][] 就假设机器人从 （50,50）开始  除了（50， 50）其余的都是‘*’ 表示未探索 然后你走到一个地方如果撞墙了就把‘*’ 改成1 else 改成0 应该大概就是这样子

扫地机器人的题不可以每次只explore三个directions：往上，往右跟往左三个direction，之后用一个traversed set来记哪些坐标呗traversed过的么？ 完了自己写一个backup的utility function，每traverse完一个点可以回到上一个位置保证facing same direction

Ostrichi 发表于 2018-1-26 07:27
这应该是不行的  我没有理解错的话 这道题的难点就是你不知道机器人一开始的坐标 也不知道房间的地图

...

你好，我有一个思路，但是在纸上画了一下但是感觉不太对。如果是简单地DFS，比如规定了访问一个点后，
←↓→↑ 这样走，基本上走下来就是一个G。 如果起始点恰好在整个房间的右边的中间的话，我就会被这个G给包围死了。我有点迷糊的是，function call的backtrack和这个机器人的回到上一个点，这两个操作如何联系起来。不能让机器人也跟着一个一个走回去吧，等于把之前的路又走了一遍。我思路还是有些混乱，希望点拨一下，谢谢。

tabletenniser 发表于 2018-2-3 01:23
扫地机器人的题不可以每次只explore三个directions：往上，往右跟往左三个direction，之后用一个traversed  ...

这样有好多的重复啊，有没有优化？比如房间没有障碍物是一个标准的矩形的情况。

jason123 发表于 2018-2-3 16:00
你好，我有一个思路，但是在纸上画了一下但是感觉不太对。如果是简单地DFS，比如规定了访问一个点后，
...

我后来想了下 不用char[][] 可以用字符串来代表是否访问过 比如你走过了(1,1), 你就在set里面加一个"1, 1"这样。
你说的机器人回到原位 我感觉有两种办法 一种递归的话就是
if(nextPosition is not visited)
moveToNextPosition
update coordinates
traverseFromNextPos
change coordinates to previous
moveToOriginalPos

补充内容 (2018-2-4 07:43):
将就看吧 伪代码

然后第二种方法就是用栈 栈里面是三个东西(curX, curY, nextDirctionToExplore) 这个说起来蛮麻烦的 推荐你上百度查一下 栈走迷宫 这里有一个不同的地方就是你需要走回去 你可以根据之前的栈的

补充内容 (2018-2-4 07:44):
第三个元素来看怎么走回去 还有你可以写boolean moveLeft() 这样的函数， 左走一格， 朝向不变 如果可以就return true 否则return false 这样会方便很多

机器人那题turnLeft或turnRight会返回什么吗？我不知道turnLeft之后对于该位置的相对位置了，比如它是朝上走的，turnLeft相对位置是{0， -1}， 但如果本来是朝左走的话，turnLeft就变成了{1， 0}