谷歌电面跪经

endofunctor 发表于 2017-8-20 11:50
测了下貌似没问题。。。后面那四个helper应该还可以优化一下，懒得优化了。。。欢迎指正
假设机器人开始向 ...

为什么需要4个helper， 每一个只扫三个方向。 为啥不能用一个helper DFS4个方向吗？
谢谢

zjswhhh 发表于 2017-8-21 23:10
菜啊这种题是编程入门题啊。。。你要是想不清机器人在哪里的话那你思路很有问题。。。弄个map[][]自己设定 ...

大哥给一个代码看看？

freipan 发表于 2018-1-5 13:46
对这段代码不理解，
                if(this.Move()){
                    dfsClean(nx, ny, nd, mem ...

跟层主一样的想法，回到上一个节点的位置和方向，suppose应该是turnRight(2) , move(), turnRight(2). 不明白原来po主为什么少了一个turnRight(2)。另外，最后两行也不太明白。既然在4次loop循环中，方向改变了3次，那最后应该恢复到原方向，也就是 this.TurnRight(1)，但为什么代码中要恢复到原方向的反方向呢？望解惑！
// orient robot to oposite direction of d
        this.TurnRight(3);

如果把房间看成一个迷宫的话， 只要不停地以右手/左手原则走，是可以遍历整个迷宫的。不知道这样算不算简化了问题。

为什么不试试dp？
first loop all cell:
      dp[r][c] = dp[r-1][c] || dp[r][c - 1] || dp[r][c + 1];
      path[r][c][i++] = {dp[r-1][c], dp[r][c - 1], dp[r][c + 1]}; // add the true cell into path[r][c]
dfs search the path until the searched node == the empty cells:

补充内容 (2018-4-17 10:17):
顺便问一下lz，你面什么级别？感觉好难啊，我也是在职跳，汪汪是我的dream，去不了我就打算回国啦，哎，希望别面到这么难的，希望是国人给我面，看到印度人怕了。

endofunctor 发表于 2017-8-20 11:50
测了下貌似没问题。。。后面那四个helper应该还可以优化一下，懒得优化了。。。欢迎指正
假设机器人开始向 ...

不懂为啥需要4个helper function啊 哪位大神能指点一下

baudelaire 发表于 2017-8-21 20:34
感觉是dfs+backtrack 不过房子太大了可能会爆栈。 写了一下代码 请大神们指教！

總覺得最後一行應該是

    turnRight((d + 2) %4);

感谢楼主分享，说一下我的思路

首先这个题本质上是一个图的遍历的问题，所以一般会想到dfs或者bfs。但是考虑到，如果用bfs，相当于需要机器人去跳跃位置 （bfs每一层的点不一定是相连的，举例说第一层是原点，第二层就是上下左右四个点，机器人是不可能从上直接跳到下继续bfs的），这个在代码实现上比较困难，所以选用dfs。扫完当前的只需要转到正确的方向，向回走一步即可。另外需要一个set来储存已经访问过的点，避免dfs进入死循环

然后不考虑机器人的话，基本的dfs算法应该是这样的
def dfs(x, y, arrived):
    if x,y out of boundary: return
    if (x,y) in arrived: return
    arrived.add(x,y)
    do something (like clean)
    dfs(x+1, y)
    dfs(x-1, y)
    dfs(x, y+1)
    dfs(x, y-1)

把这个算法套用到机器人身上，有几个需要注意的地方：
1. 关于测试是不是out of boundary，需要调用move函数看返回值，也就是说其实是在调用下一层dfs之前尝试，成功就进入，否则是停留在原地
2. dfs算法中，没有考虑如何回来（四条递归代码跑完了，自己就回来了），但是机器人需要指明回来的道路，所以可能还需要额外一个参数表示进来时的方向（0,1,2,3 应该就可以表示上右下左），而递归函数出来时候的方向，应该就是进去方向相反，出来之后调整方向进入下一个递归或者退回上一层

将这些考虑进去之后，代码应该是这样的 (api 调用可能不太规范，看个大致意思)
主程序：
arrived=set([])
dfs(0,0,arrived, 0) ##假设初始位置是0,0， 方向向上


def dfs(x, y, arrived, direction):
  if (x,y) in arrived:
    ##扫过的点，直接掉头回去， 左转右转两下都可以,走回去，再转半圈回到最初进来之前的方向
    turnleft(2)
    move()
        turnleft(2)
        return
  
  ##没扫过，那么了解一下
  arrived.add((x,y))
  clean(x,y)
  
  ##调整到向上的方向
  turnleft(direction)
  
  ##向上试一试
  if move():
    dfs(x+1,y,arrived,0)

  ##向右试一试
  turnright(1)
  if move():
    dfs(x,y+1,arrived,1)

  ##向下试一试       
  turnright(1)
  if move():
    dfs(x-1,y,arrived,2)
  
  ##向左试一试
  turnright(1)
  if move():
    dfs(x,y-1,arrived,3)
  
  turnright(1)
  ##这时候方向是调整到朝上的，需要变成进来时相反的方向，
  turnright((direction+2)%4)
  move() ##这个应该不用试，肯定能回去
  turnright(2)  
  ##方向回正
  
大概就是这样，希望大家指正
另外刚才在写的时候还有点想法，可以讨论一下：
感觉是不是有可能不用direction， 因为不管你怎么走进去， 其实不需要一定按照上右下左来遍历，就按照当前方向试一下，右转试一下，再右转试一下这样就行，最后回到原来的方向，但是这样有个难点是没有direction的帮助，不知道下一层的xy是怎么变化的，所以可能还是需要额外信息。