fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. typedef std::pair<int, int> int_pair;
  5. typedef std::vector< std::vector<int> > int_matrix;
  6.  
  7. void traceback (int row, int col, std::vector<int_pair>& base_pairs, int_matrix& dp_matrix ){
  8.   // bounds checking?
  9.  
  10.   if(dp_matrix[row+1][col-1] == dp_matrix[row][col]){
  11.     int_pair base_pair = {row,col};
  12.     base_pairs.push_back(base_pair);
  13.     traceback(row+1, col-1, base_pairs, dp_matrix);
  14.     return;
  15.   }
  16. }
  17.  
  18. int main() {
  19.   int_matrix dp_matrix{{4,3,2,1},
  20.                        {3,2,1,1},
  21.                        {2,1,2,3},
  22.                        {0,2,3,4}};
  23.   std::vector<int_pair> base_pairs;
  24.   traceback(0, 3, base_pairs, dp_matrix);
  25.   for (auto& pair : base_pairs)
  26.     std::cout << pair.first << "," << pair.second << std::endl;
  27. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0,3
1,2
https://ideone.com/6gYmXP
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!