Fluyd Warshell Algo | Very Easy Solution
Problem Intuition\n\nThe problem can be seen as finding the shortest path between pairs of nodes in a graph. Here, nodes represent points on a grid, and edges r
### Problem Intuition\n\nThe problem can be seen as finding the shortest path between pairs of nodes in a graph. Here, nodes represent points on a grid, and edges represent direct connections between nodes. The grid is initialized such that each pair of adjacent nodes has a direct edge with a weight of 1. Additionally, a special edge with weight 1 is added between nodes `x` and `y`.\n\nThe task is to count the number of pairs of nodes that have a specific shortest path length. To achieve this, we can use the Floyd-Warshall algorithm to find the shortest paths between all pairs of nodes and then count the occurrences of each path length.\n\n### Approach\n\n1. **Grid Initialization**:\n    - Create a 2D vector `grid` of size `(n+1) x (n+1)` to represent the distances between nodes, initialized to a large value (`100000`) to represent infinity.\n    - Set the direct connections between adjacent nodes to 1, indicating that there is a direct path of length 1 between them. Also, add a direct connection between the special pair `(x, y)`.\n\n2. **Shortest Path Calculation (Floyd-Warshall Algorithm)**:\n    - Use three nested loops to iterate through all possible pairs of nodes `(i, j)` and check if a shorter path exists through an intermediate node `via`. Update `grid[i][j]` with the minimum distance found.\n\n3. **Counting Pairs**:\n    - Create a result vector `result` to store the count of pairs for each path length.\n    - Iterate through all pairs of nodes `(i, j)`. For each pair, if `i` is not equal to `j`, get the shortest path length from `grid[i][j]`, and increment the corresponding index in `result`.\n\n4. **Return the Result**:\n    - The result vector will contain the count of pairs for each path length.\n\n### Time Complexity\n\n- The **Floyd-Warshall algorithm** runs in `O(n^3)` time because it iterates through all possible triplets `(i, j, via)` to update the shortest paths.\n- The **counting pairs step** takes `O(n^2)` time because it involves iterating through all pairs of nodes.\n\nThus, the overall time complexity of the solution is `O(n^3)`.\n\n### Space Complexity\n\n- The space complexity is `O(n^2)` due to the storage of the `grid` matrix of size `(n+1) x (n+1)` and the `result` vector of size `n`.\n\nThis approach efficiently calculates the shortest paths and counts the pairs with specific path lengths for the given problem constraints.\n\n### Code Explanation\n\n```cpp\nclass Solution {\npublic:\n    vector<int> countOfPairs(int n, int x, int y) {\n        // Initialize the grid with a large value (infinity)\n        vector<vector<int>> grid(n+1, vector<int>(n+1, 100000));\n        \n        // Set direct connections between adjacent nodes\n        for(int j = 1; j < n; j++) {\n            grid[j][j+1] = 1;\n            grid[j+1][j] = 1;\n        }\n        // Set the special direct connection between x and y\n        grid[x][y] = 1;\n        grid[y][x] = 1;\n        \n        // Floyd-Warshall algorithm to calculate shortest paths\n        for(int via = 1; via <= n; via++) {\n            for(int i = 1; i <= n; i++) {\n                for(int j = 1; j <= n; j++) {\n                    // Update the shortest path between i and j\n                    grid[i][j] = min(grid[i][j], grid[i][via] + grid[via][j]);\n                }\n            }\n        }\n        \n        // Create a result vector to store counts of pairs for each path length\n        vector<int> result(n);\n        for(int i = 1; i <= n; i++) {\n            for(int j = 1; j <= n; j++) {\n                if(i != j) {\n                    // Get the shortest path length between i and j\n                    int val = grid[i][j];\n                    // Increment the count for this path length\n                    result[val-1]++;\n                }\n            }\n        }\n        \n        return result;\n    }\n};\n```\n\n
['Breadth-First Search', 'Graph', 'Prefix Sum', 'Shortest Path', 'C++']