矩阵，BFS 最短距离探索
这题乍看之下特别像滑雪，于是想试试用 DFS + memoization，于是有了下面的代码，过了 25/62 个 test cases ，错在了一个
[0 , INF, 0, INF, INF]
[-1, -1 , 0 , -1 , INF]
[-1 , 0 , 0 , 0 , INF]
[-1 , INF , 0 , 0 , -1]
这样的 test case 上。
其原因是，当我们搜索 (0, 4) 这个位置时，dfs 搜索了相邻的 (0, 5)，这时候遇到了比较尴尬的境地:
为了避免死循环，我们要把当前元素改一下，免得下一步的 dfs 重新探回来；
但是在这个局部上，正解却偏偏要探回来，往左走才能碰到最近的 0.
于是我们发现了这题和滑雪最大的不同：滑雪由于取值限制，是不用担心回头路的，但这题会。留回头路会死循环，不留回头路会算错。
于是下面的代码在如上的 test case 上会挂掉；
public class Solution {
public void wallsAndGates(int[][] rooms) {
for(int i = 0; i < rooms.length; i++){
for(int j = 0; j < rooms[0].length; j++){
if(rooms[i][j] == Integer.MAX_VALUE) rooms[i][j] = memoizedSearch(rooms, i, j);
}
}
}
private int memoizedSearch(int[][] rooms, int x, int y){
if(x < 0 || x >= rooms.length) return Integer.MAX_VALUE;
if(y < 0 || y >= rooms[0].length) return Integer.MAX_VALUE;
if(rooms[x][y] == 0) return 0;
if(rooms[x][y] == -1) return Integer.MAX_VALUE;
if(rooms[x][y] == Integer.MAX_VALUE){
rooms[x][y] = -1;
int N = memoizedSearch(rooms, x - 1, y);
int S = memoizedSearch(rooms, x + 1, y);
int W = memoizedSearch(rooms, x, y - 1);
int E = memoizedSearch(rooms, x, y + 1);
int min = Math.min(Math.min(N, S), Math.min(W, E));
if(min == Integer.MAX_VALUE){
rooms[x][y] = Integer.MAX_VALUE;
return rooms[x][y];
} else {
rooms[x][y] = min + 1;
return rooms[x][y];
}
} else {
return rooms[x][y];
}
}
}“和最短距离” 相关的问题，最靠谱的还是BFS 解法。
一个最容易想到的做法是，每个 INF 为起点，扫整个矩阵。每个起点走的最长距离是 O(mn)，总共有 O(mn) 个能的起点，所以复杂度为 O(m^2 * n^2)，太慢了。
改良版本是，我们不从 INF 的角度开始，而是反过来，从 0 开始往回找，沿路只添加看到的 INF; 由于是 BFS，从gate出发，第一次看到某个房间的时候就是最短距离。这样我们有 O(mn) 个可能的起点和位置要搜，然而每个位置只会进入队列一次，所以时间和空间复杂度都是 O(mn).
每个位置只看一次，并不一定要靠记忆化搜索，DFS / BFS flood filling 一样可以。事实上，大多数都是靠 flood filling，靠记忆化搜索的反而是少数。
另一个小技巧是，处理矩阵不一定非要拍成一维 index，队列里直接扔 int[] 也完全可以，还省事。
public class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0) return;
int rows = rooms.length;
int cols = rooms[0].length;
Queue<int[]> queue = new LinkedList<>();
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(rooms[i][j] == 0) queue.offer(new int[]{i, j});
}
}
int distance = 1;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int[] cur = queue.poll();
int[] xDir = {0,0,-1,1};
int[] yDir = {-1,1,0,0};
for(int j = 0; j < 4; j++){
int[] next = {cur[0] + xDir[j], cur[1] + yDir[j]};
if(next[0] >= 0 && next[1] >= 0 && next[0] < rows && next[1] < cols){
if(rooms[next[0]][next[1]] == Integer.MAX_VALUE){
rooms[next[0]][next[1]] = distance;
queue.offer(next);
}
}
}
}
distance ++;
}
}
}先说一下自己第一个不成功的尝试，那就是一维推导错了，以为是所有 X 坐标的平均值。
在一维情况下：
只有一个点
取当前点的位置；
有两个点
两点之间的任何位置都是等价的，等于区间大小；
有三个点
最外面两点之间的任意位置等价，距离和等于区间大小；
于是剩下一个点，可以发现最优位置就是在点上；
有 N 个点
我们可以对于排序了的坐标从外向里配对消除，每一对的距离等于这对点形成的区间大小。
于是我我们可以总结为：
点的个数为偶数，则最里面 pair 之间的任意位置等价；
点的个数为奇数，则一定在最里面的中心点上；
因此，最优点就是当前维度的中位数。
于是一个最直观的解法就是，记录所有的 "1" 的 X/Y 坐标，选中位数，再把所有的地方过一遍。
扫哪里是 1 + 用两次 quick select + 计算总的距离
O(mn) + O(m) + O(n) + O(m) + O(n) = O(mn)
不过从提交速度上看，这个解法速度不理想，而且写个 quick select 代码量就上去了，面试时候有点浪费时间。
public class Solution {
public int minTotalDistance(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
List<Integer> listX = new ArrayList<>();
List<Integer> listY = new ArrayList<>();
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){
listX.add(i);
listY.add(j);
}
}
}
int medianX = findMedian(listX, 0, listX.size() - 1);
int medianY = findMedian(listY, 0, listY.size() - 1);
int minDis = 0;
for(int x : listX){
minDis += Math.abs(medianX - x);
}
for(int y : listY){
minDis += Math.abs(medianY - y);
}
return minDis;
}
private int findMedian(List<Integer> list, int start, int end){
int pivot = list.get(start);
int left = start;
int right = end;
while(left <= right){
while(left <= right && list.get(left) <= pivot) left++;
while(left <= right && list.get(right) >= pivot) right--;
if(left < right) swap(list, left, right);
}
swap(list, start, right);
int medianIndex = list.size() / 2;
if(right == medianIndex){
return list.get(right);
} else if(right < medianIndex){
return findMedian(list, right + 1, end);
} else {
return findMedian(list, start, right - 1);
}
}
private void swap(List<Integer> list, int a, int b){
int temp = list.get(a);
list.set(a, list.get(b));
list.set(b, temp);
}
}论坛上还有一个很有趣的解法，虽然时间复杂度不好看，但是思路巧妙，简洁易懂。
核心思想在于，最优 meeting point 一定是在所有点的中间，而对于每个 pair ，他们到 best meeting point 的距离和就是 pair 两点的区间长度，所以假设以 0 为远点，用双指针检查每一对就可以了。
public int minTotalDistance(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> I = new ArrayList<>(m);
List<Integer> J = new ArrayList<>(n);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
I.add(i);
J.add(j);
}
}
}
return getMin(I) + getMin(J);
}
private int getMin(List<Integer> list){
int ret = 0;
Collections.sort(list);
int i = 0;
int j = list.size() - 1;
while(i < j){
ret += list.get(j--) - list.get(i++);
}
return ret;
}如果进一步利用循环的特点，甚至排序都可以省了，ArrayList 里自动就是排好序的。不过会扫两次 O(mn)，就有一个取舍的问题在里面了。
public class Solution {
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
List<Integer> I = new ArrayList<Integer>();
List<Integer> J = new ArrayList<Integer>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
I.add(i);
}
}
}
for(int j = 0; j < n; j++) {
for(int i = 0; i < m; i ++) {
if(grid[i][j] == 1) {
J.add(j);
}
}
}
return minTotalDistance(I) + minTotalDistance(J);
}
public int minTotalDistance(List<Integer> grid) {
int i = 0, j = grid.size() - 1, sum = 0;
while(i < j) {
sum += grid.get(j--) - grid.get(i++);
}
return sum;
}
}乍看之下是上一题的强化版，因为所谓“距离”的定义是一样的，都是曼哈顿距离。最主要的不同点在于，中间有障碍之后，问题就不再是简单的分开维度拆分分析了，因为对于每一个位置，都要考虑障碍物的具体位置。
因此不难看出，这题变成了一个 Graph 问题，因为对于矩阵中任意两点 A & B，其最短距离只有靠 BFS 去查。 矩阵就是一种 uniform weight, undirected graph.
一个非常土的办法是，先扫一遍矩阵，找到 k 个起始点；对于每一个起始点开始做 BFS，记录到每一个其他格子的距离，每次扫完了要存这个位置到起点的距离，并且每次扫完一个点要恢复矩阵的访问状态，免得下一次扫描出错，扫到第 k 个起点的时候，把每个 cell 里面的相对于其他店的距离加起来，保持一个 min 就可以了。
时间复杂度： 2k * O(mn) ，考虑到 k 可能等于整个矩阵，其实是 O(m^2 * n^2)
空间复杂度： k * O(mn)，考虑到 k 可能等于整个矩阵，其实时 O(m^2 * n^2)
我觉得这个思路可以不用写代码了，肯定要超时的。。
这个时间复杂度和暴力解 Walls and Gates 一样，不难想到，可以试着从每个 "1" 出发，去反过来探索矩阵。 假如我们记录了这 k 个起始点，我们可以依次 bfs 每一个起始点 / 该起始点的范围，一次一个点，一次扩张一轮，当 k 个点的 “势力范围” 第一次相交的时候，就是我们要找的最优起点。有了最优起点，O(mn) 的时间显然就可以算出最短距离。
问题一 : 如何保证对于固定起点的 BFS 过程中，不走回头路，而且相邻边界不重复添加；
问题二：如何解决多个起点 BFS 之间的覆盖问题？
问题三：对于某一个被若干个队列中边界点包围的位置，我们怎么判断每次试图访问的时候，是同一个起点的重复访问（此时跳过），还是另一个起点的回合点（此时保留）？
可以看到，在 Walls and Gates 中，这两个问题是不存在的，因为当一个位置被某个 BFS 发现之后，最短距离就确定了，后面的所有 BFS 也都不会再去访问了，一口气解决了 “相邻边界重复添加” 和 “不同起点覆盖搜索” 两个问题。
经过了半天的思考之后，依然没能找到接近 O(mn) 的解法，于是我就跑去 LC 论坛看答案了。你妹啊，你们用的也是我一开始的挫算法。。。。所以如果真是面试头一次碰到这种题，不要犹豫，就先撸个最暴力的办法再说。
痛定思痛，一次撸完AC，速度超过 89.66%
开个 int[][] 记录每个位置相对于每个点的最短距离，每一个 (i , j) 的值只会在一次探索中被更新一次，取值叠加；
用负数作为 flag ，代表探索进度。有两个明显的好处：
剪枝，扫第 5 个起点的时候，对于 flag = -2 的位置，连扫的必要都没有；
去重，每个起点的 BFS 都需要机制来避免重复添加，而 flag 是天然的状态指示，如果当前位置的 flag 和当前 BFS 的有效 flag 不相等，则直接跳过，起到了一个 undirected graph bfs 中的 0, 1, 2 状态功能~
每个起点的 BFS 都会更新其所有能碰到的 “有效点” 的最短距离，一个点在一次迭代中只会被访问一次。
因此最后只要扫一下 flag 矩阵，flag == curMark 的就是合理位置，找其对应的 disMap[][] 值，记录最小就可以了。
另一个优化是，可以在每一轮的 BFS 过程中检查当前最短距离，省去最后收尾扫描。不过对用时影响不大就是了，下面的代码没写那部分。
public int shortestDistance(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int[][] disMap = new int[rows][cols];
int minDis = Integer.MAX_VALUE;
int curMark = 0;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(grid[i][j] == 1){
bfs(grid, disMap, i, j, curMark);
curMark --;
}
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(grid[i][j] == curMark) minDis = Math.min(minDis, disMap[i][j]);
}
}
return minDis == Integer.MAX_VALUE ? -1 : minDis;
}
private void bfs(int[][] grid, int[][] disMap, int x, int y, int curMark){
int rows = grid.length;
int cols = grid[0].length;
int distance = 1;
Queue<int[]> queue = new LinkedList<>();
// Just found out using curMark can save the use of visited
queue.offer(new int[]{x, y});
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int[] cur = queue.poll();
int curX = cur[0];
int curY = cur[1];
int[] xDirs = {0,0,1,-1};
int[] yDirs = {-1,1,0,0};
for(int j = 0; j < 4; j++){
int nextX = curX + xDirs[j];
int nextY = curY + yDirs[j];
if(nextX >= 0 && nextX < rows &&
nextY >= 0 && nextY < cols &&
grid[nextX][nextY] == curMark){
grid[nextX][nextY] = curMark - 1;
disMap[nextX][nextY] += distance;
queue.offer(new int[]{nextX, nextY});
}
}
}
distance ++;
}
}Last updated
Was this helpful?