矩阵中两元素最小曼哈顿距离
http://massivealgorithms.blogspot.com/2015/12/leetcode-317-shortest-distance-from-all.html
还有我看了近三个月的面经，感觉 数字翻转那个题（1981旋转180°之后是1861） 和 矩阵里找两个元素的最小曼哈顿距离的题 有点高频啊，后面面试的同学仔细看看吧
我也印象见过矩阵里找两个元素的最小曼哈顿距离的题几次。
原帖找不到了但是大意是这个：
矩阵里面有0，1，2，3
0表示可以通过
3表示障碍物不能穿行。
现在需要你找离1最短的2.
我觉得最直接的应该就是对每个1进行bfs， 然后返回距离最近的2， 然后比较得出最短的距离。
还有一种想法就是能不能同时对所有2同时进行bsf，首先遇到的1就是最短距离，这个思路和bidirectional bsf差不多，只是同时搜索。
其实就是变图中单源最短路径为多源最短路径
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=511673
正式的题是一个二维矩阵上面有X， Y，O，问从X到Y的最短距离（曼哈顿距离）
楼主说的应该是有很多的X, Y求其中曼哈顿距离最小的一对pair吧。这个题也看到过很多次了
https://www.jiuzhang.com/qa/885/
http://massivealgorithms.blogspot.com/2015/12/leetcode-317-shortest-distance-from-all.html
还有我看了近三个月的面经，感觉 数字翻转那个题（1981旋转180°之后是1861） 和 矩阵里找两个元素的最小曼哈顿距离的题 有点高频啊，后面面试的同学仔细看看吧
我也印象见过矩阵里找两个元素的最小曼哈顿距离的题几次。
原帖找不到了但是大意是这个：
矩阵里面有0，1，2，3
0表示可以通过
3表示障碍物不能穿行。
现在需要你找离1最短的2.
323003130001 <- 最左边的1是离右下角的2最短距离的。000333330002 |
我觉得最直接的应该就是对每个1进行bfs， 然后返回距离最近的2， 然后比较得出最短的距离。
还有一种想法就是能不能同时对所有2同时进行bsf，首先遇到的1就是最短距离，这个思路和bidirectional bsf差不多，只是同时搜索。
其实就是变图中单源最短路径为多源最短路径
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=511673
正式的题是一个二维矩阵上面有X， Y，O，问从X到Y的最短距离（曼哈顿距离）
楼主说的应该是有很多的X, Y求其中曼哈顿距离最小的一对pair吧。这个题也看到过很多次了
https://www.jiuzhang.com/qa/885/
初阶：在一个n*m的矩阵中，有k个点，求矩阵中距离这k个点的距离和最近的点。
进阶：如果要求这个点与所给的k个点不重合，该怎么办？
注：这里的距离采用曼哈顿距离——|x0-x1| + |y0-y1|
初阶：因为采用曼哈顿距离，所以可以分开考虑x坐标和y坐标。将k个点的x坐标排序，可以知道要求的x坐标一定在这k个点的x坐标上，扫描一遍并统计到各个点的x坐标距离和，找到使得距离和最小的x坐标。这一步只需要O(k)的时间复杂度，而不是O(k^2)，怎么优化这里不多赘述。对y坐标做同样的操作，从而得到答案。时间复杂度O(klogk)，排序的复杂度。
进阶：通过初阶的算法得到一个最优位置，如果这个位置与k个点重合，则从这个位置开始进行搜索，将这个点周围的点和对应的距离放入到一个堆里，每次从堆中取出最小距离的点，然后将这个点周围的点放入堆中，直到取出的点不与所给k个点重合。时间复杂度klogk，因为最多从堆中取出k+1个点即可找到一个不与所给k个点重合的点。堆每次操作为logk。
面试官角度：
本题的最优算法较难想到。所以如果公司要求不高，答出O(nm)的方法即可。O(nm)的方法是因为假设我们知道在(x,y)这个位置的距离和为S，那么当(x,y)移动到(x+1,y)和(x,y+1)的时候，我们可以在O(1)的时间更新S。方法是预处理每一行上方/下方有多少个k个点中的点，每一列左侧/右侧有多少个k个点中的点。上面的解答基于nm>>klogk，如果k比较大，则还是O(nm)的方法更好。答题时需要答出对于给定参数不同情况下采用不用算法这一点。
