找到给定节点网格和一组源节点的最大距离
Find maximum distance given a grid of nodes and a set of source nodes
给定一组排列为 m×n 网格的节点(注意:对角线节点 未 连接),以及一组标记为 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。
对于具有 1 个以上源的网格,例如 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;
}
}
}
}
}
有没有更快的算法可以解决这个问题?
是您可以使用称为多源 BFS 的概念解决此问题。多源 BFS 的概念与 BFS 类似,但这里有细微差别。
在普通 BFS 中,我们最初只将 1 个节点推送到队列中,而在多源 BFS 中,我们推送所有源节点。
所以把所有的源节点push之后我们就可以正常做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;
}
}
给定一组排列为 m×n 网格的节点(注意:对角线节点 未 连接),以及一组标记为 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。
对于具有 1 个以上源的网格,例如 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;
}
}
}
}
}
有没有更快的算法可以解决这个问题?
是您可以使用称为多源 BFS 的概念解决此问题。多源 BFS 的概念与 BFS 类似,但这里有细微差别。
在普通 BFS 中,我们最初只将 1 个节点推送到队列中,而在多源 BFS 中,我们推送所有源节点。
所以把所有的源节点push之后我们就可以正常做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;
}
}