2d array ＊代表障碍物 ＃代表货物 空白就是正常的路. 问如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍需要绕开，拿到以后要放回出发点，然后再取另一个.

＊＊＊＊＊＊
＊   ＃  ＊
＊ ＊＊＊ ＊
＊       ＊
＊ ＊＊   ＊
＊ ＃   ＃＊
＊＊ ＊＊＊＊


关于解法的相关讨论如下:

--

每个货物都是独立的，就是找有障碍的曼哈顿距离. 

--

一种解法是用BFS, 对每一个障碍物路径简单求和. 
取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，
所以可以一个一个来bfs碰到一个就加2x的长度，碰到k个为止.

--

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

--

这个方法肯定是对的，唯一可以优化的是，可以在每个节点中存一个距离的array,
vector<int> d(k, 0). 存该点到每个box的最小距离。这样的话，在bfs一开始就把所
有的box先放进queue里一起做bfs。应该扫一遍就可以了。最后在扫一遍整个matrix，
每个节点求个和，找最小的distance

typedef struct node {
    bool visited;
    vector<int> d(k, 0);
    int x;
    int y;
} node;

--

发信人: euclid2003 (Superbia et Fiducia), 信区: JobHunting
标  题: Re: 热腾腾g电面 已挂
发信站: BBS 未名空间站 (Tue Feb 25 11:39:04 2014, 美东)

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<CacheKey, Integer> cache = new HashMap<CacheKey,
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<matrix.length; i++){
            for (int j=0; j<matrix[i].length; 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<matrix.length; i++){
            int j = 0;
            for (; j<matrix[i].length-1; 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<Integer, Integer> distances;
   
    public static int[][] randomMatrix(int size){
        matrix = new int[size][size];
        for (int i=0; i<size; i++){
            for (int j=i+1; j<size; 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<matrix.length; i++){
            for (int j=0; j<matrix[i].length-1; 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<Integer, Integer>();
        distances.put((Integer) 0, (Integer) 0);
        for (int i=0; i<matrix.length; i++){
            for (int j=i+1; j<matrix[i].length; 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();
     }
}

--

本文内容来自: http://www.mitbbs.com/article_t/JobHunting/32631467.html

Same as this: 
https://leetcode.com/problems/shortest-distance-from-all-buildings/