online compiler and debugger for c/c++

#include <fstream> #include <vector> #include <string> #include <algorithm> #include <cmath> using namespace std; // Define constants const int MAX = 1005; // Maximum number of rows or columns const double INF = 1e9; // A very large number to be used as initial minimum distance const vector<string> DIRECTION = {"S", "SE", "SW"}; // Possible moves const vector<int> dx = {1, 1, 1}; // For each move, x (row) is increased by 1 const vector<int> dy = {0, 1, -1}; // For each move, y (column) could be same, increase by 1, or decrease by 1 // Declare global variables double dp[MAX][MAX]; // dp[i][j] will store minimum distance from the top to cell (i, j) int trace[MAX][MAX]; // trace[i][j] will store previous column for the optimal path to cell (i, j) int start[MAX][MAX]; // start[i][j] will store starting column for the optimal path to cell (i, j) double cost[MAX][MAX]; // cost[i][j] will store traversal time for cell (i, j) void solve(int r, int c) { // Initialize the top row cells with their own traversal time // The optimal path to each cell in the top row is the cell itself for (int j = 0; j < c; j++) { dp[0][j] = cost[0][j]; start[0][j] = j; } // Now, fill rest of the dp table row by row for (int i = 1; i < r; i++) { for (int j = 0; j < c; j++) { dp[i][j] = INF; // Start with a very large distance // Try all possible moves for (int k = 0; k < 3; k++) { int y = j + dy[k]; // Next column based on the move if (y >= 0 && y < c) { // If it's a valid column // Calculate extra cost for the move double extra_cost = k == 0 ? cost[i][j] : 1.4 * cost[i][j]; // If the new distance is smaller than current distance if (dp[i - 1][y] + extra_cost < dp[i][j]) { dp[i][j] = dp[i - 1][y] + extra_cost; // Update minimum distance trace[i][j] = y; // Update previous column start[i][j] = start[i - 1][y]; // Update starting column } } } } } } // Function to get the optimal path ending at column c pair<int, vector<string>> get_path(int r, int c) { vector<string> path; // Vector to store the moves int cur = c; // Start from column c // Trace the path from bottom to top for (int i = r - 1; i > 0; i--) { int prev = trace[i][cur]; // Get the previous column path.push_back(DIRECTION[prev < cur ? 1 : (prev == cur ? 0 : 2)]); // Get the move from previous cell to current cell cur = prev; // Move to previous cell } reverse(path.begin(), path.end()); // Reverse the path to get from top to bottom // Return starting column and the path return make_pair(start[r - 1][c], path); } int main() { // Open input and output files ifstream input("input-small.txt"); ofstream output("output.txt"); // Read number of rows and columns int r, c; input >> r >> c; // Read traversal time for each cell for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) input >> cost[i][j]; // Solve the problem solve(r, c); // For each column on the bottom row, get the optimal path and write to output file for (int i = 0; i < c; i++) { pair<int, vector<string>> res = get_path(r, i); output << dp[r - 1][i] << " " << res.first; // Write total traversal time and starting column for (string &s : res.second) // Write moves output << " " << s; output << "\n"; // Start a new line for the next column } // Close input and output files input.close(); output.close(); return 0; }