SHARE
TWEET

Untitled

a guest Feb 16th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. / Concurs Mate-Info - aprilie 2015
  2.  
  3. // Subiectul 3 - Matrice rara
  4.  
  5.  
  6.  
  7. /**
  8.  
  9.  * Se dau 2 matrice rare, se cere afisarea sumei lor sub forma unul tablou dimensional
  10.  
  11.  *
  12.  
  13.  *
  14.  
  15.  *
  16.  
  17.  * Exemplu : {
  18.  
  19.  *  n = m = 3
  20.  
  21.  * Matricea A
  22.  
  23.  * 2 2 2
  24.  
  25.  * 3 3 3
  26.  
  27.  * 1 2 5
  28.  
  29.  * 3 1 2
  30.  
  31.  * 1 3 5
  32.  
  33.  * -1-1-1
  34.  
  35.  * Matricea B
  36.  
  37.  * 3 2 4
  38.  
  39.  * 1 2 -5
  40.  
  41.  * 2 2 1
  42.  
  43.  * -1-1-1
  44.  
  45.  *
  46.  
  47.  * }
  48.  
  49.  *
  50.  
  51.  *
  52.  
  53.  *
  54.  
  55. */
  56.  
  57.  
  58.  
  59.  
  60.  
  61. #include <iostream>
  62.  
  63. using namespace std;
  64.  
  65.  
  66.  
  67. struct triplet {
  68.  
  69.     int row,
  70.  
  71.         col,
  72.  
  73.         val;
  74.  
  75.     triplet * next;
  76.  
  77. };
  78.  
  79.  
  80.  
  81. triplet * getLastNode(triplet * start) {
  82.  
  83.     triplet * temp = start;
  84.  
  85.     while(temp->next) temp = temp->next;
  86.  
  87.     return temp;
  88.  
  89. }
  90.  
  91.  
  92.  
  93. triplet *  add(triplet * start,int row, int col, int val) {
  94.  
  95.  
  96.  
  97.     // Create new node
  98.  
  99.     triplet * new_node = new triplet;
  100.  
  101.  
  102.  
  103.     new_node->row = row;
  104.  
  105.     new_node->col = col;
  106.  
  107.     new_node->val = val;
  108.  
  109.  
  110.  
  111.     // If the list has not been created yet
  112.  
  113.     if(!start) {
  114.  
  115.         start = new_node;
  116.  
  117.         start->next = NULL;
  118.  
  119.         return start;
  120.  
  121.     } else {
  122.  
  123.         // If the list has been created, get the last node and make the connection
  124.  
  125.         triplet *last = getLastNode(start);
  126.  
  127.         last->next = new_node;
  128.  
  129.         last = new_node;
  130.  
  131.         last ->next = NULL;
  132.  
  133.     }
  134.  
  135.  
  136.  
  137. }
  138.  
  139.  
  140.  
  141.  
  142.  
  143. void printList(triplet * st) {
  144.  
  145.     triplet *temp = st;
  146.  
  147.     for(; temp; temp=temp->next) {
  148.  
  149.         cout << temp->row << " ";
  150.  
  151.         cout << temp->col << " ";
  152.  
  153.         cout << temp->val << " ";
  154.  
  155.         cout << "\n";
  156.  
  157.     }
  158.  
  159. }
  160.  
  161.  
  162.  
  163. void getInput(triplet **start1,triplet **start2, int &n, int &m) {
  164.  
  165.     // Dimensions of the matrix
  166.  
  167.     cin >> n >> m;
  168.  
  169.  
  170.  
  171.     // When the next triplet is encounterd : -1-1-1
  172.  
  173.     // It means we're going to get the input from the second matrix
  174.  
  175.     int breakpoits = 0;
  176.  
  177.     int col,row,val;
  178.  
  179.  
  180.  
  181.     while(1) {
  182.  
  183.  
  184.  
  185.         if(breakpoits == 2) {
  186.  
  187.             break;
  188.  
  189.         }
  190.  
  191.         cin >> row >> col >> val;
  192.  
  193.  
  194.  
  195.         // Breakpoint encountered
  196.  
  197.         if(row == col && col == val && val == -1) {
  198.  
  199.             breakpoits++;
  200.             continue;
  201.  
  202.         }
  203.  
  204.  
  205.  
  206.         // Deferencing the pointer that points to this pointer... I know how it sounds!
  207.  
  208.         // *start = add(*start,etc..)
  209.  
  210.  
  211.  
  212.         // Determine for which matrix we are getting input
  213.  
  214.         if(breakpoits == 0) {
  215.  
  216.             // First sparse matrix
  217.  
  218.             if(!*start1) {
  219.  
  220.                 // The list has not been created yet
  221.  
  222.                 *start1 = add(*start1,row,col,val);
  223.  
  224.             }
  225.  
  226.             else add(*start1,row,col,val);
  227.  
  228.  
  229.  
  230.         } else if(breakpoits == 1) {
  231.  
  232.             // Second sparse matrix
  233.  
  234.             if(!*start2) {
  235.  
  236.                 // The list has not been created yet
  237.  
  238.                 *start2 = add(*start2,row,col,val);
  239.  
  240.             }
  241.  
  242.             else add(*start2,row,col,val);
  243.  
  244.         }
  245.  
  246.  
  247.  
  248.     }
  249.  
  250. }
  251.  
  252.  
  253.  
  254. // Check if a list has a certain column and row
  255.  
  256. int searchInList(triplet * start, int row, int col) {
  257.  
  258.  
  259.  
  260.     triplet *temp = start;
  261.  
  262.     while(temp) {
  263.  
  264.         if(temp->row == row && temp->col == col)
  265.  
  266.             return temp->val;
  267.  
  268.         // Keep searching
  269.  
  270.         temp = temp->next;
  271.  
  272.     }
  273.  
  274.  
  275.  
  276.     // Row & Column have not been found
  277.  
  278.     return 0;
  279.  
  280. }
  281.  
  282.  
  283.  
  284. void solve() {
  285.  
  286.  
  287.  
  288.     triplet *start1=NULL, *start2 = NULL;
  289.  
  290.     int n,m;
  291.  
  292.     // getInput(**startPointer1,**startPointer2) : **startPointer holds the address of start
  293.  
  294.     getInput(&start1,&start2,n,m);
  295.  
  296.  
  297.  
  298.     // Final sparse matrix containing the sum of the other 2 sparse matrix
  299.  
  300.     int **finalMatrix = new int *[n]; // Rows
  301.  
  302.     for(int i =0; i < n; i++) {
  303.  
  304.         // Create a new row
  305.  
  306.         finalMatrix[i] = new int[m]; // Number of columns
  307.  
  308.         for(int j=0; j < m; j++) {
  309.  
  310.  
  311.  
  312.             // If a row & col have not been found in any of the 2 lists
  313.  
  314.             // c[row][col] = 0
  315.  
  316.  
  317.  
  318.             // Search for row and col
  319.  
  320.             int value_from_first = searchInList(start1,i+1,j+1);
  321.  
  322.             int value_from_second = searchInList(start2,i+1,j+1);
  323.  
  324.             finalMatrix[i][j] =  value_from_first + value_from_second;
  325.  
  326.         }
  327.  
  328.     }
  329.  
  330.  
  331.  
  332.     // Print the matrix
  333.  
  334.     for(int i =0 ; i < n; i++) {
  335.  
  336.         for(int j =0; j < m; j++) {
  337.  
  338.             cout << finalMatrix[i][j] << " ";
  339.  
  340.         }
  341.  
  342.         cout << "\n";
  343.  
  344.     }
  345.  
  346.     delete finalMatrix;
  347.  
  348. }
  349.  
  350.  
  351.  
  352.  
  353.  
  354. int main () {
  355.    
  356.     solve();
  357.  
  358.     return 0;
  359.  
  360. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top