门冲点面

target e5 yoe6 hr reach out

// # A DashMart is a warehouse run by DoorDash that houses items found in
// # convenience stores, grocery stores, and restaurants. We have a city with open
// # roads, blocked-off roads, and DashMarts.
// #
// # City planners want you to identify how far a location is from its closest
// # DashMart.
// #
// # You can only travel over open roads (up, down, left, right).
// #
// # Locations are given in [row, col] format.
// #
// # Example:
// #
// # [
// # # 0 1 2 3 4 5 6 7 8
// # ['X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'], # 0
// # ['X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'], # 1
// # [' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '], # 2
// # [' ', ' ', ' ', 'D', ' ', 'X', ' ', ' ', ' '], # 3
// # [' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'], # 4
// # [' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X'] # 5
// # ]
// #
// # ' ' represents an open road that you can travel over in any direction (up, down, left, or right).
// # 'X' represents an blocked road that you cannot travel through.
// # 'D' represents a DashMart.
// #
// # # list of pairs [row, col]
// # locations = [
// # [2, 2],
// # [4, 0],
// # [0, 4],
// # [2, 6],
// # ]
// #
// # answer = [1, 4, 1, 5]
// #
// # Implement Function:
// # - get_closest_dashmart(city, locations)
// #
// # Provided:
// # - city: List[str]
// # - locations: List[List[int]]
// #
// # Return:
// # - answer: List[int]

需要注意的是墙也算valid location

请问楼主面试之后多久收到结果呢

最短路径，还挺简单的

这个是leetcode的题吧。类似于286

典型bfs，这么简单啊

1. public class DashMart {
   
2. 
   
3.     private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // Right, Down, Left, Up
   
4. 
   
5.     public static int[] closestDashMart(char[][] city, int[][] locations) {
   
6.         int rows = city.length;
   
7.         int cols = city[0].length;
   
8.         int[] results = new int[locations.length];
   
9.         int[][] distances = new int[rows][cols];
   
10.         boolean[][] visited = new boolean[rows][cols];
    
11.         Queue<int[]> queue = new LinkedList<>();
    
12. 
    
13.         // Initialize BFS from each DashMart location
    
14.         for (int i = 0; i < rows; i++) {
    
15.             for (int j = 0; j < cols; j++) {
    
16.                 if (city[i][j] == 'D') {
    
17.                     queue.add(new int[] {i, j});
    
18.                     visited[i][j] = true;
    
19.                     distances[i][j] = 0;
    
20.                 }
    
21.             }
    
22.         }
    
23. 
    
24.         // Perform BFS to calculate minimum distances to a DashMart
    
25.         while (!queue.isEmpty()) {
    
26.             int[] current = queue.poll();
    
27.             int row = current[0];
    
28.             int col = current[1];
    
29. 
    
30.             for (int[] direction : DIRECTIONS) {
    
31.                 int newRow = row + direction[0];
    
32.                 int newCol = col + direction[1];
    
33. 
    
34.                 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol] && city[newRow][newCol] == ' ') {
    
35.                     visited[newRow][newCol] = true;
    
36.                     distances[newRow][newCol] = distances[row][col] + 1;
    
37.                     queue.add(new int[]{newRow, newCol});
    
38.                 }
    
39.             }
    
40.         }
    
41. 
    
42.         // Retrieve distances for given locations
    
43.         for (int i = 0; i < locations.length; i++) {
    
44.             int locRow = locations[i][0];
    
45.             int locCol = locations[i][1];
    
46.             if (locRow < rows && locCol < cols && visited[locRow][locCol]) {
    
47.                 results[i] = distances[locRow][locCol];
    
48.             } else {
    
49.                 results[i] = -1; // Unreachable or out of bounds
    
50.             }
    
51.         }
    
52. 
    
53.         return results;
    
54.     }
    
55. 
    
56.     public static void main(String[] args) {
    
57.         char[][] city = {
    
58.                 {'X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'},
    
59.                 {'X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'},
    
60.                 {' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '},
    
61.                 {' ', ' ', ' ', 'D', ' ', 'X', ' ', ' ', ' '},
    
62.                 {' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'},
    
63.                 {' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X'}
    
64.         };
    
65. 
    
66.         int[][] locations = {
    
67.                 {2, 2},
    
68.                 {4, 0},
    
69.                 {0, 4},
    
70.                 {2, 6}
    
71.         };
    
72. 
    
73.         int[] results = closestDashMart(city, locations);
    
74.         for (int result : results) {
    
75.             System.out.println(result);
    
76.         }
    
77.     }
    
78. }

复制代码