根据给定的节点网格和一组源节点找到最大距离

Question

给定一组以m×n网格排列的节点集（注意：对角线节点是not连接的），以及标记为source节点的一组节点，求出最大距离节点和源节点之间。

例如，对于4 x 4网格和（1，0）处的源节点：

0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0

计算每个节点到其最接近源的距离将产生：

1 2 3 4
0 1 2 3
1 2 3 4
2 3 4 5

因此，最大距离为5。

[对于具有多个源的网格，例如3个源节点：

0 0 1 0
1 0 0 0
0 0 0 0
0 0 0 1

计算每个节点到其最接近源的距离将产生：

1 1 0 1
0 1 1 2
1 2 2 1
2 2 1 0

因此，最大距离为2。

[我写出了一种算法来解决这个问题，但是看起来最坏的情况是它在O（n ^ 4）中运行（假设m == n）：

// MaximumDistances.java

public class MaximumDistances {
    public static void main(String[] args) {
        int[][] sourceNodes = new int[][] {
            {0, 0, 1, 0},
            {1, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 1}
        };

        int maximumDistance = computeMaximumDistance(sourceNodes);
        System.out.println(String.format(
            "The maximum distance in this grid is %d.",
            maximumDistance));
    }

    private static int computeMaximumDistance(int[][] sourceNodes) {
        int m = sourceNodes.length;
        int n = sourceNodes[0].length;

        // Initializes the distance grid. Since none of the sites have been
        // visited yet, the distance to any grid cell with be
        // `Integer.MAX_VALUE`.
        int[][] distanceGrid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                distanceGrid[i][j] = Integer.MAX_VALUE;
            }
        }

        // If we're at a source site, we mark its distance to each grid cell.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (sourceNodes[i][j] == 1) {
                    markDistancesFromSourceSite(i, j, distanceGrid);
                }
            }
        }

        // The maximum value in the distance grid will be the maximum distance.
        int maximumDistance = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (distanceGrid[i][j] > maximumDistance) {
                    maximumDistance = distanceGrid[i][j];
                }
            }
        }

        return maximumDistance;
    }

    private static void markDistancesFromSourceSite(int x, int y, int[][] distanceGrid) {
        int m = distanceGrid.length;
        int n = distanceGrid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int distanceToSource = Math.abs(x - i) + Math.abs(y - j);

                if (distanceGrid[i][j] > distanceToSource) {
                    distanceGrid[i][j] = distanceToSource;
                }
            }
        }
    }
}

是否有更快的算法可以解决这个问题？

Answer 1

是，您可以使用称为多源BFS的概念来解决此问题。多源BFS的概念与BFS相似，但这只是次要的区别。在普通BFS中，我们最初只是在队列中推送1个节点，而在多源BFS中，我们推送所有源节点。因此，在推送所有源节点之后，我们只需执行常规的BFS操作即可解决该问题。时间复杂度将为O（n * m）。

import java.util.*;
class Pair{

    int x , y , dist;

    Pair(int first , int second){

        this.x = first;
        this.y = second;
        this.dist = 0;
    }

    Pair(int first , int second , int dist){

        this.x = first;
        this.y = second;
        this.dist = dist;
    }
}

public class MultisourceBFS {
    public static void main(String[] args) {
        int[][] sourceNodes = new int[][] {
            {0, 0, 1, 0},
            {1, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 1}
        };

        int maximumDistance = computeMaximumDistance(sourceNodes);
        System.out.println(String.format(
            "The maximum distance in this grid is %d.",
            maximumDistance));
    }

    private static int computeMaximumDistance(int[][] sourceNodes) {
        int m = sourceNodes.length;
        int n = sourceNodes[0].length;

        int maximumDistance = 0;

        int xx[] = {0 , 0 , 1 , -1}; // Normal array to go to up , down , left , right;
        int yy[] = {1 , -1 , 0 , 0}; // Normal array to go to up ,down , left , right

        Queue<Pair> q = new LinkedList<Pair>();
        boolean isVisited[][] = new boolean[m][n]; // An array to check if a cell is visited or not .

        // I am adding all the source nodes to the queue

        for(int i = 0 ; i < m ; ++i)
            for(int j = 0 ; j < n ; ++j)
                if(sourceNodes[i][j]==1){
                    q.add(new Pair(i , j));
                    isVisited[i][j] = true;
                }

        // Now it is going to be normal BFS

        while(!q.isEmpty()){

            Pair node = q.remove();

            for(int k = 0 ; k < 4 ; ++k){

                int new_i = node.x + xx[k];
                int new_j = node.y + yy[k];

                if(new_i >= 0 && new_i < m && new_j >= 0 && new_j < n && isVisited[new_i][new_j]==false){

                    maximumDistance = Math.max(node.dist + 1 , maximumDistance);

                    isVisited[new_i][new_j] = true;

                    q.add(new Pair(new_i , new_j , node.dist + 1));
                }
            }
        }


        return maximumDistance;
    }

}