谷歌电面

扫地机器人。

Robot Clearner

Givena robot cleaner in a room modeled as a grid. Each cell in the grid can be emptyor blocked. The robot cleaner can move forward, turn left or turn right. Whenit tries to move into a blocked cell, its bumper sensor detects the obstacleand it stays on the current cell.

Thecontrol API:

interfaceRobot {

  //returns true if next cell is open and robot moves into the cell.

  //returns false if next cell is obstacle and robot stays on the current cell.

  booleanMove();

  //Robot will stay on the same cell after calling Turn*. k indicates how

  //many turns to perform.

  voidTurnLeft(int k);

  voidTurnRight(int k);

  //Clean the current cell.

  voidClean();more.

  booleanMove(Direction d);

}

Sampleinput

++++++++++

+........+

+...^....+

+.+......+

++++.+++++

+.....+

+++++++

. 1point 3acres 璁哄潧

要求用给定的API打扫完所有empty格子。Timecomplexity, linear in term of room space.

lingyidu 发表于 2018-2-10 06:14
DFS做吧，没有corner case啥的，最后问了复杂度，怎么测试程序

我觉得可以dfs 需要一个存路径 一个存已经访问过的点 复杂度最差是 O(n) 如果n 是房间大小， 因为每个点最多只会经过八次 但是怎么测试程序呢？

greynut 发表于 2018-2-8 03:47
电面都这么难吗直接上 Roomba??

楼主能分享以下思路 和corner case 什么的吗

DFS做吧，没有corner case啥的，最后问了复杂度，怎么测试程序

ichliebeczh 发表于 2018-2-27 06:27
我也被问了这个，没好好准备T^T
请问是只问了这一个吗楼主？

是 一道题 电面好像bar不高的

楼主是什么思路做的呀？

同求思路

wwwww 发表于 2018-1-15 13:06
楼主是什么思路做的呀？

DFS做的。

他有没有问需不需要机器人不走冤枉路？或者求走最少路的方法？

电面都这么难吗直接上 Roomba??

楼主能分享以下思路 和corner case 什么的吗

请问楼主过店面了吗  准备onsite 吗

我也被问了这个，没好好准备T^T
请问是只问了这一个吗楼主？