g*****i
发帖数: 91 | 1 同胞面试官，上来就gdoc做题。
2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
问
如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍
需要绕开，拿到以后要放回出发点，然后再取另一个
＊＊＊＊＊＊
＊ ＃ ＊
＊ ＊＊＊ ＊
＊ ＊
＊ ＊＊ ＊
＊ ＃ ＃＊
＊＊ ＊＊＊＊
大牛们有什么好思路？我用的bfs，但因为之前讨论题目要求花了很久，没有写完。。
我还是太弱了，move on | f********f
发帖数: 290 | | r****c
发帖数: 2585 | | e*****i
发帖数: 182 | 4 取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，所以可以一个一个来
bfs碰到一个就加2x的长度，碰到k个为止
【在 g*****i 的大作中提到】
: 同胞面试官，上来就gdoc做题。
: 2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
: 问
: 如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍
: 需要绕开，拿到以后要放回出发点，然后再取另一个
: ＊＊＊＊＊＊
: ＊ ＃ ＊
: ＊ ＊＊＊ ＊
: ＊ ＊
: ＊ ＊＊ ＊
| w********s
发帖数: 1570 | 5 你取一个的结果计算过程是否对取下一个有用，有用的话，记录下来下一次不用那么耗
费。
【在 e*****i 的大作中提到】
: 取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，所以可以一个一个来
: bfs碰到一个就加2x的长度，碰到k个为止
| l**********a
发帖数: 181 | | q******n
发帖数: 116 | | r****c
发帖数: 2585 | | g*****i
发帖数: 91 | 9 都不需要 找出那个点
【在 r****c 的大作中提到】
: 需要具体路径还是只要长度
| g*****i
发帖数: 91 | 10 google了一下才知道啥时候曼哈顿距离
【在 r****c 的大作中提到】
: 每个货物都是独立的，就是找有障碍的曼哈顿距离
| | | l******6
发帖数: 340 | 11 bfs from every box. in each box , a non blocking cell(include box position ,
but exclude hazard position ) will have a weight value , stand for the
distance to the box. after bfs from all the boxes , each cell will have k
weight, k is the number of boxes. sum all the weight in each cell , and find
the cell with smallest sum of weight. One problem of this solution may lead
to a cell of a box. revision is sort the cell by sum of weight and find the
first that is not a box.
complexity k*n^2 | n*****a
发帖数: 107 | 12 正解，这个题目就是从起点（默认的左上角那个）做bfs好了，时间复杂度就是矩阵的
单元格的数量
【在 e*****i 的大作中提到】
: 取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，所以可以一个一个来
: bfs碰到一个就加2x的长度，碰到k个为止
| f*****e
发帖数: 2992 | 13 只是一个电面题，应该不难，心理上不要有包袱。
【在 n*****a 的大作中提到】
: 正解，这个题目就是从起点（默认的左上角那个）做bfs好了，时间复杂度就是矩阵的
: 单元格的数量
| j*********n
发帖数: 34 | | f******n
发帖数: 53 | 15 map[7][6]
000000
012110
000010
011110
010010
021120
000000
//Assume 2 is product, 1 is blank, 0 is block. 2 is also block before
fetching
use BFS
result start at map[4][4]
order map[1][2] map[5][4] map[5][1] total 20 steps
【在 j*********n 的大作中提到】
: 从#开始做BFS
| w********f
发帖数: 60 | 16 这个方法肯定是对的，唯一可以优化的是，可以在每个节点中存一个距离的array,
vector d(k, 0). 存该点到每个box的最小距离。这样的话，在bfs一开始就把所
有的box先放进queue里一起做bfs。应该扫一遍就可以了。最后在扫一遍整个matrix，
每个节点求个和，找最小的distance
typedef struct node {
bool visited;
vector d(k, 0);
int x;
int y;
} node;
,
find
lead
the
【在 l******6 的大作中提到】
: bfs from every box. in each box , a non blocking cell(include box position ,
: but exclude hazard position ) will have a weight value , stand for the
: distance to the box. after bfs from all the boxes , each cell will have k
: weight, k is the number of boxes. sum all the weight in each cell , and find
: the cell with smallest sum of weight. One problem of this solution may lead
: to a cell of a box. revision is sort the cell by sum of weight and find the
: first that is not a box.
: complexity k*n^2
| o*****n
发帖数: 189 | | g*****i
发帖数: 91 | 18 谢谢你！还是需要多练习
【在 o*****n 的大作中提到】
: 同意14楼。LZ估计是太紧张了。
| g*****i
发帖数: 91 | 19 受教了！多谢！
图片是05年的伊斯坦布尔吧 我也是米兰球迷
【在 f******n 的大作中提到】
: map[7][6]
: 000000
: 012110
: 000010
: 011110
: 010010
: 021120
: 000000
: //Assume 2 is product, 1 is blank, 0 is block. 2 is also block before
: fetching
| n*****a
发帖数: 107 | 20 这个是对的，我原来看错题目了，以为从一个设定好的点出发，求到所有货物的最短距
离了，不好意思。
,
find
lead
the
【在 l******6 的大作中提到】
: bfs from every box. in each box , a non blocking cell(include box position ,
: but exclude hazard position ) will have a weight value , stand for the
: distance to the box. after bfs from all the boxes , each cell will have k
: weight, k is the number of boxes. sum all the weight in each cell , and find
: the cell with smallest sum of weight. One problem of this solution may lead
: to a cell of a box. revision is sort the cell by sum of weight and find the
: first that is not a box.
: complexity k*n^2
| | | b*****t
发帖数: 296 | 21 这题是O（m+n）吧，穷举法，先算x再算y，因为曼哈顿距离是可以投影得，
带入法，先算在列上，那个点到所有货物点得横坐标距离和最小，得到横坐标值；同理
得到纵坐标值，如果该点不能访问，比较x次优，x最优，y次优，y最优的坐标组合，选
没有block的最小结果。 | t*****j
发帖数: 1105 | 22 虽然这题不算太难，我的想法也是对每个货物BFS，然后扫描算最小sum。
可是咱同胞，还只是个电面就面这个，说实话，我想骂人。 | e********3
发帖数: 18578 | 23 BFS+DP,而且需要maintain两个距离，一个是到终点的最小距离，一个是到起点的最小
距离，计算终点的距离需要backtrack,到起点的简单比较保存最小值就行了，类似
Dijkstra算法。电面就考这个有点偏难了，尤其还是同胞就操蛋了，要是老中这么考老
印我绝对赞成。简单的实现还可以把障碍物那个的距离设成100啥的，这样自然就知道
要绕过了。
这个题目的难度比reverse linkedlist, atoi难了几个数量级。。。
我贴两个我自己写的代码抛砖引玉一下，第一个是Harry Potter最小的strength通关，
第二个是经典的Dijkstra algorithm,都是附带了测试数据自动生成的方法，你把这两
个组合一下基本就能解这道题了,过两天我有空了来写一下这道题的具体实现。
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMap
Integer>();
static class CacheKey{
private int x, y;
public CacheKey(int x, int y){
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj){
CacheKey key = (CacheKey) obj;
return this.x == key.x && this.y == key.y;
}
@Override
public int hashCode(){
return ((Integer) (this.x+this.y)).hashCode();
}
}
public static int[][] createMatrix(int width, int height){
int[][] matrix = new int[height][width];
for (int i=0; i
for (int j=0; j
matrix[i][j] = rand.nextInt(50);
if (rand.nextBoolean()){
matrix[i][j] *= -1;
}
}
}
return matrix;
}
public static void printMatrix(int[][] matrix){
for (int i=0; i
int j = 0;
for (; j
System.out.print(matrix[i][j] + ", ");
}
System.out.println(matrix[i][j]);
}
}
public static int minimumStrength(int x, int y){
int strength = 0;
if (x == matrix[0].length-1 && y == matrix.length-1){
if (matrix[y][x] < 0){
strength = -1 * matrix[y][x];
}
} else if (x == matrix[0].length-1){
int nextStrength = cachedStrength(x, y+1);
strength = calcStrength(nextStrength, x, y);
} else if (y == matrix[0].length-1){
int nextStrength = cachedStrength(x+1, y);
strength = calcStrength(nextStrength, x, y);
} else {
int nextStrength = Math.min(cachedStrength(x, y+1),
cachedStrength(x+1, y));
strength = calcStrength(nextStrength, x, y);
}
System.out.println(x + ", " + y + " needs minimum strength of " +
strength);
return strength;
}
public static int cachedStrength(int x, int y){
CacheKey key = new CacheKey(x, y);
if (cache.containsKey(key)){
return cache.get(key);
} else {
int strength = minimumStrength(x, y);
cache.put(key, strength);
return strength;
}
}
private static int calcStrength(int nextStrength, int x, int y){
int strength = 0;
if (nextStrength == 0){
if (matrix[y][x] < 0) strength = -1 * matrix[y][x];
} else {
if (matrix[y][x] - nextStrength >= 0){
strength = 0;
} else {
strength = nextStrength - matrix[y][x];
}
}
return strength;
}
public static void main(String []args){
int size = 3;
matrix = createMatrix(size,size);
printMatrix(matrix);
cachedStrength(0,0);
}
}
-------------------------------------------------------------------------
import java.util.*;
public class Dijkstra{
private static Random rand = new Random();
private static int[][] matrix;
private static Map distances;
public static int[][] randomMatrix(int size){
matrix = new int[size][size];
for (int i=0; i
for (int j=i+1; j
matrix[i][j] = rand.nextInt(20) + 1;
if (i == 0) {
//Applies weight, otherwise, the final distance is
usually the same as the first row.
matrix[i][j] += (j-1) * 15;
}
}
}
return matrix;
}
public static void printMatrix(int[][] matrix){
for (int i=0; i
for (int j=0; j
System.out.print(Math.abs(matrix[i][j]) + ", ");
}
System.out.println(matrix[i][matrix[i].length-1]);
}
System.out.println("-----------------------------");
}
public static void minPath() throws RuntimeException{
distances = new HashMap();
distances.put((Integer) 0, (Integer) 0);
for (int i=0; i
for (int j=i+1; j
if (matrix[i][j] > 0){
if (distances.get((Integer) j) == null){
distances.put((Integer) j, distances.get((Integer) i
) + matrix[i][j]);
} else {
if (distances.get((Integer) i) == null) {
throw new RuntimeException();
} else {
if (distances.get((Integer) i) + matrix[i][j] <
distances.get((Integer) j)){
distances.put((Integer) j, distances.get((
Integer) i) + matrix[i][j]);
}
}
}
}
}
}
System.out.println(distances.toString());
}
public static void main(String []args){
printMatrix(randomMatrix(5));
minPath();
matrix = new int[6][6];
matrix[0][1] = 7;
matrix[0][2] = 9;
matrix[0][5] = 14;
matrix[1][2] = 10;
matrix[1][3] = 15;
matrix[2][3] = 11;
matrix[2][5] = 2;
matrix[3][4] = 6;
matrix[4][5] = 9;
printMatrix(matrix);
minPath();
}
}
【在 g*****i 的大作中提到】
: 同胞面试官，上来就gdoc做题。
: 2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
: 问
: 如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍
: 需要绕开，拿到以后要放回出发点，然后再取另一个
: ＊＊＊＊＊＊
: ＊ ＃ ＊
: ＊ ＊＊＊ ＊
: ＊ ＊
: ＊ ＊＊ ＊
|
|
