一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1188|回复: 2
收起左侧

google foobar题目

[复制链接] |试试Instant~ |关注本帖
wujingzhishui 发表于 2016-9-27 01:01:38 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - Other - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
同学在google foobar上的一道题, 提交时候一直是400 bad request,估计是超时了,分享给我题目和他的解法,求优化
Prepare the Bunnies' Escape
===========================

You're awfully close to destroying the LAMBCHOPdoomsday device and freeing Commander Lambda's bunny prisoners, but oncethey're free of the prison blocks, the bunnies are going to need to escapeLambda's space station via the escape pods as quickly as possible.Unfortunately, the halls of the space station are a maze of corridors and deadends that will be a deathtrap for the escaping bunnies. Fortunately, CommanderLambda has put you in charge of a remodeling project that will give you theopportunity to make things a little easier for the bunnies. Unfortunately(again), you can't just remove all obstacles between the bunnies and the escapepods - at most you can remove one wall per escape pod path, both to maintainstructural integrity of the station and to avoid arousing Commander Lambda'ssuspicions.

You have maps of parts of the space station, each starting at a prison exit andending at the door to an escape pod. The map is represented as a matrix of 0sand 1s, where 0s are passable space and 1s are impassable walls. The door outof the prison is at the top left (0,0) and the door into an escape pod is atthe bottom right (w-1,h-1). 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

Write a function answer(map) that generates the length of the shortest pathfrom the prison door to the escape pod, where you are allowed to remove onewall as part of your remodeling plans. The path length is the total number ofnodes you pass through, counting both the entrance and exit nodes. The startingand ending positions are always passable (0). The map will always be solvable,though you may or may not need to remove a wall. The height and width of themap can be from 2 to 20. Moves can only be made in cardinal directions; nodiagonal moves are allowed.
Test cases
==========. Waral 鍗氬鏈夋洿澶氭枃绔,

Inputs:
    (int) maze = [[0, 1, 1, 0], [0, 0, 0,1], [1, 1, 0, 0], [1, 1, 1, 0]].1point3acres缃
Output:
    (int) 7. 1point3acres.com/bbs

Inputs:
    (int) maze = [[0, 0, 0, 0, 0, 0], [1,1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0,0, 0, 0, 0, 0]]. From 1point 3acres bbs
Output:
    (int) 11
未通过答案:(其实我两都在自己机子上通过的,跑的很快,方法就是dfs变形):
public static int answer(int[][] maze) {

        // Your code goes here.
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfs(0, 0, true, visited, maze, 1);
    }
    private static int dfs(int x, int y, boolean allowRemove, boolean[][] visited, int[][] maze, int len){
        if(x == maze.length - 1 && y == maze[0].length - 1){
            return len;
        }
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        visited[x][y] = true;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < 4; i++){
           int nx = dx + x;
           int ny = dy + y;
           if(nx < 0 || ny < 0 || nx >= maze.length || ny >= maze[0].length || visited[nx][ny]){
               continue;
           }
           if(maze[nx][ny] == 0){
               min = Math.min(dfs(nx, ny, allowRemove, visited, maze, len + 1), min);
           }else if(allowRemove){
               min = Math.min(dfs(nx, ny, false, visited, maze, len + 1), min);
           }
           if(min == maze.length + maze[0].length - 1){
               break;
           }
        }
        visited[x][y] = false;
        return min;
    }

评分

1

查看全部评分

WhatsFLAG 发表于 2016-9-27 04:02:42 | 显示全部楼层
第一次听说Foobar,Google了一下感觉赞爆了!
回复 支持 反对

使用道具 举报

kolanery 发表于 2016-10-1 08:19:45 | 显示全部楼层
400 bad request好像是foobar的bug...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 00:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表