#include #include #include #include using namespace std; struct State { int x, y; char method; int time, cost; State(int x, int y, char method, int time, int cost) : x(x), y(y), method(method), time(time), cost(cost) {} }; struct StateComparator { bool operator()(const State& a, const State& b) { if (a.time != b.time) { return a.time > b.time; } return a.cost > b.cost; } }; class Solution { private: static const int dirs[4][2]; bool isValidMove(int x, int y, int height, int width, vector>& visited, vector>& grid) { return x >= 0 && x < height && y >= 0 && y < width && !visited[x][y] && grid[x][y] != 'X'; } public: string findOptimalCommute(vector> grid, vector modes, vector costs, vector times) { if (grid.empty() || grid[0].empty()) return ""; vector source, destination; int height = grid.size(); int width = grid[0].size(); // Find source and destination positions for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (grid[i][j] == 'S') { source = {i, j}; } else if (grid[i][j] == 'D') { destination = {i, j}; } } } if (source.empty() || destination.empty()) return ""; if (source[0] == destination[0] && source[1] == destination[1]) return modes[0]; // Prioritize by time first, then by cost priority_queue, StateComparator> pq; vector> visited(height, vector(width, false)); visited[source[0]][source[1]] = true; // Initialize with neighbors of source for (int i = 0; i < 4; i++) { int nextX = source[0] + dirs[i][0]; int nextY = source[1] + dirs[i][1]; if (isValidMove(nextX, nextY, height, width, visited, grid)) { char transportMode = grid[nextX][nextY]; if (transportMode != 'X') { pq.push(State(nextX, nextY, transportMode, 0, 0)); } } } // Dijkstra's algorithm while (!pq.empty()) { State current = pq.top(); pq.pop(); if (visited[current.x][current.y]) { continue; } visited[current.x][current.y] = true; // Check if reached destination if (current.x == destination[0] && current.y == destination[1]) { return modes[current.method - '1']; } // Explore neighbors with same transportation mode for (int i = 0; i < 4; i++) { int nextX = current.x + dirs[i][0]; int nextY = current.y + dirs[i][1]; if (isValidMove(nextX, nextY, height, width, visited, grid)) { char nextCell = grid[nextX][nextY]; // Can move to destination or same transportation mode if (nextCell == 'D' || nextCell == current.method) { int modeIndex = current.method - '1'; pq.push(State(nextX, nextY, current.method, current.time + times[modeIndex], current.cost + costs[modeIndex])); } } } } return ""; } }; const int Solution::dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

AI Assistant