2019/1/7 狗家店面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. package Graph.UG;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. public class FindShortestDistance {
   
6. 
   
7.     private char X = 'X';
   
8.     private char Y = 'Y';
   
9. 
   
10.     private int [] xCoordinate = {-1, 1, 0, 0};
    
11.     private int [] yCoordinate = {0, 0, -1, 1};
    
12. 
    
13.     public int shortestDistance(char [][] matrix) {
    
14. 
    
15.         int n = matrix.length;
    
16.         int m = matrix[0].length;
    
17. 
    
18.         int [][] output = new int[n][m];
    
19.         boolean [][] visited = new boolean[n][m];
    
20. 
    
21.         Queue<int []> queue = new LinkedList<>();
    
22.         for (int i = 0; i < n; i ++) {
    
23.             for (int j = 0; j < m; j ++) {
    
24.                 if (matrix[i][j] == X) {
    
25.                     queue.offer(new int [] {i, j});
    
26.                     visited[i][j] = true;
    
27.                 }
    
28.             }
    
29.         }
    
30. 
    
31.         int distance = 0;
    
32. 
    
33.         while (!queue.isEmpty()) {
    
34.             int size = queue.size();
    
35. 
    
36.             for (int i = 0; i < size; i ++) {
    
37.                 int [] currentPosition = queue.remove();
    
38.                 if (matrix[currentPosition[0]][currentPosition[1]] == Y) {
    
39.                     return distance;
    
40.                 }
    
41. 
    
42.                 for (int k = 0; k < 4; k ++) {
    
43.                     int newX = currentPosition[0] + xCoordinate[k];
    
44.                     int newY = currentPosition[1] + yCoordinate[k];
    
45. 
    
46.                     if (isValid(matrix, newX, newY) && visited[newX][newY] == false) {
    
47.                         queue.offer(new int[] {newX, newY});
    
48.                         visited[newX][newY] = true;
    
49.                     }
    
50.                 }
    
51.             }
    
52.             distance ++;
    
53.         }
    
54. 
    
55.         return distance;
    
56.     }
    
57. 
    
58.     private boolean isValid(char [][] matrix, int x, int y) {
    
59.         int n = matrix.length;
    
60.         int m = matrix[0].length;
    
61. 
    
62.         return (x >= 0 && x < n && y >= 0 && y < m);
    
63.     }
    
64. 
    
65.     public static void main(String [] args) {
    
66.         char[][] maze = {{'X','O','O','O'} ,{'X','O','O','O'} ,{'O','O','O','Y'}};
    
67. 
    
68.         FindShortestDistance t = new FindShortestDistance();
    
69.         System.out.println(t.shortestDistance(maze));
    
70.     }
    
71. }
    

复制代码

rachelxiaoyu 发表于 2019-2-15 16:10
[mw_shl_code=java,true]package Graph.UG;

import java.util.*;

写了一下这个题，请大家指教，时间复杂度 O(m*n), 空间复杂度 O(m*n),

曼哈顿距离这题不知道有没有除了bfs更好的解法

有个疑问请教大家，曼哈顿距离不是应该Abs|x1 - y1| + Abs|x2 - y2|么， 这个结果和Abs|(x1 + y1) - (x2 + y2)|不同吧。比如我的X在（2，5）， Y 在（3，4）。曼哈顿距离是2而不是0.所以怎么可以用排序加BS办法么？只能BFS吧？

rachelxiaoyu 发表于 2019-2-15 16:10
[mw_shl_code=java,true]package Graph.UG;

import java.util.*;

写的真好，清晰漂亮

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies