• API
• FAQ
• Tools
• Archive
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.
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.
223.
224.             }
225.
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.
239.
240.             }
241.
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.

Top