用java编写,输入格式:第一行是两个以空格符分隔的整数n和m;接下来的第二行到第m+1行,每行包含4个以空格分开的元素x,y,w和d来描述一条道路,其中x和y是一条长度为w的道路相连的两个农场的编号,d是字符N.E.S.或W,表示从x到y的道路的方向。输出格式:给出最远的一对农场之间距离的整数。
时间: 2024-01-21 16:16:19 浏览: 125
编译原理试验 删除空格
以下是Java代码实现:
```java
import java.util.*;
public class FarmlandDistance {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] graph = new int[n+1][n+1];
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int w = sc.nextInt();
char d = sc.next().charAt(0);
if (d == 'N') {
graph[x][y] = w;
graph[y][x] = w;
} else if (d == 'E') {
graph[x][y] = w;
} else if (d == 'S') {
graph[x][y] = -w;
graph[y][x] = -w;
} else if (d == 'W') {
graph[y][x] = w;
}
}
int maxDistance = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] != 0 && graph[k][j] != 0) {
graph[i][j] = Math.max(graph[i][j], graph[i][k] + graph[k][j]);
maxDistance = Math.max(maxDistance, graph[i][j]);
}
}
}
}
System.out.println(maxDistance);
}
}
```
解释一下代码的思路:
首先,我们用一个二维数组 `graph` 来表示农场之间的道路,其中 `graph[i][j]` 表示从农场 i 到农场 j 的道路长度。如果两个农场之间没有道路,则 `graph[i][j]` 的值为 0。
接下来,我们通过输入的道路信息来构建 `graph` 数组。如果一条道路的方向是 N,则将农场 x 和 y 之间的道路长度都设置为 w,因为这是双向的道路。如果方向是 E,则只需要将 `graph[x][y]` 设置为 w。如果方向是 S,则将农场 x 和 y 之间的道路长度都设置为 -w,表示这是双向的道路且方向相反。如果方向是 W,则将 `graph[y][x]` 设置为 w。
最后,我们使用 Floyd 算法来计算最远的一对农场之间的距离。具体来说,我们使用三重循环来遍历所有可能的农场对,然后在每次循环中更新 `graph` 数组中的元素。如果从农场 i 到农场 k 和从农场 k 到农场 j 都有道路,则可以通过农场 k 缩短从农场 i 到农场 j 的距离。我们将更新后的距离与 `maxDistance` 比较,以确定最远的一对农场之间的距离。
最终,我们输出 `maxDistance` 即可。
阅读全文