谷歌电面跪经

如果没有grid的信息，怎么知道哪里是障碍物，哪里是emtpy啊，

我的想法是dfs traversal, 当从dfs离开, 要回到之前的点, 并且将robot的方向, 找到call dfs时的方向, 不知道各位觉得如何?

void robotClean(vector<vector<char>>& mm, Robot& r){
        vector<vector<int>> visited(mm.size(), vector<int>(mm[0].size()));
        int cr = -1, cl = -1;
        for (int i = 0 ; i < mm.size() ; i++){
                for (int j = 0 ; j < mm[0].size() ; j++){
                        if (mm[i][j] == '^'){
                                cr = i; cl = j;
                                break;
                        }
                }
                if (cr>=0 && cj >=0)
                        break;
        }
        dfs(r, cr, cl, visited, 0);
        return;
}

void dfs(Robot& r, int row, int col, vector<vector<int>>& visited, Direction dir)
{
        int dd[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
        r.clean();
        visited[nr][nr] = 1;
        for (int i = 0 ; < 4 ; i++){
                if (i != 0){
                        r.TurnRight(1);
                        dir =  (dir + 1)%4;
                }
                int nr = row + dd[dir][0];
                int nl = col + dd[dir][1];
                if (!visited[nr][nl]){
                        if (r.move()){
                                dfs(r, nr, nl, visited, dir);
                        }
                }
        }
        r.TurnLeft(1);
        r.move();
        r.TurnRight(2);
        return;

}


补充内容 (2017-8-16 14:08):
假定一开始机器人是朝上

补充内容 (2017-8-16 14:23):
原来是不能输入 grid的 那这个方法不行了,

赞楼主。 电面就是运气，有些Google电面题目不难，甚至leetcode原题。 加油

reliveinfire 发表于 2017-8-16 14:04
我的想法是dfs traversal, 当从dfs离开, 要回到之前的点, 并且将robot的方向, 找到call dfs时的方向, 不知 ...

感觉dfs()里，一直可以 call move() and clean() 打扫卫生直到robot either move to the next cell that has a block or the next cell is already cleaned, 在这两种情况下robot就要turnLeft and turnRight, 所以这里move()一次好像有问题

补充内容 (2017-8-17 04:49):
不过实在有点confused about turnLeft(k) and turnRight(k), 这个参数k啥意思 求解答

我有个疑问。如果一开始不知道机器人在哪的话。怎么做？

haifengc 发表于 2017-8-15 21:58
如果没有grid的信息，怎么知道哪里是障碍物，哪里是emtpy啊，

可以调用boolean Move()去让机器人试，true说明是empty并且机器人前进一格，false说明是障碍物并且机器人原地不动。

luckchaser 发表于 2017-8-16 12:48
感觉dfs()里，一直可以 call move() and clean() 打扫卫生直到robot either move to the next cell that  ...

turnRight(int k)是用来robot转身k次。比如，turnRight(2)就可以让机器人在原地向右转两次（180度）。

这题更像一个机器学习的题目，用神经网络或者遗传算法解决的。

不zhiwei何 发表于 2017-8-17 05:24
turnRight(int k)是用来robot转身k次。比如，turnRight(2)就可以让机器人在原地向右转两次（180度）。

明白啦，谢谢解疑