SHARE
TWEET

Untitled

bbescos Jan 20th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Compiled with: g++ -Wall -std=c++14 -pthread
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. //This is NOT an in-place algorithm
  10. //x' = x*cos(a) - y*sin(b)
  11. //y' = x*sin(a) + y*cos(b)
  12. //With this we rotate around the center of the matrix
  13. //If matrix is n x n. Memory Complexity O(n^2)
  14. //Runtime Complexity O(n^2)
  15. void rotate(vector<vector<int>>& matrix) {
  16.     // Copia
  17.     vector<vector<int>> _matrix = matrix;
  18.     for (int i = 0; i < matrix.size(); ++i){
  19.         for (int j = 0; j < matrix.size(); ++j){
  20.             matrix[i][j] = _matrix[matrix.size() - 1 - j][i];
  21.         }
  22.     }
  23. }
  24.  
  25.  
  26. //This is an in-place algorithm
  27. //If matrix is n x n. Memory Complexity O(1)
  28. //Runtime Complexity O(n^2)
  29. //This is faster because the second for loop iterates as maximum n/2.
  30. void rotate_2(vector<vector<int>>& matrix) {
  31.    
  32.     // swap -> 1 variable extra y 2 assignments
  33.     // 3 swaps -> 6 cambios (9)
  34.     // ---------> 4 + 1 temp (5)
  35.     //
  36.     int n = matrix.size();
  37.     for (int i = 0; i < n; ++i){
  38.         for (int j = i + 1; j < n - i; ++j){
  39.             // aqui ya se donde tiene que ir cada uno de estos 4 numeros
  40.             // (i,j), (j, n-1-i), (n-1-i, n-1-j), (n-1-j, i)
  41.             // 3 swaps
  42.             // int temp = matrix[i][j];
  43.             // matrix[i][j] = matrix[n - 1 - j][i];
  44.             // matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
  45.             // matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
  46.             // matrix[j][n - 1 - i] = temp;
  47.             swap(matrix[i][j], matrix[j][n - 1 - i]);
  48.             swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
  49.             swap(matrix[i][j], matrix[n - 1 - j][i]);
  50.         }
  51.     }
  52. }
  53.  
  54.  
  55. //This is an in-place algorithm
  56. //If matrix is n x n. Memory Complexity O(1)
  57. //Runtime Complexity O(n^2)
  58. void rotate_flipao(vector<vector<int>>& matrix) {
  59.     int n = matrix.size();
  60.     for (int i = 0; i < n; ++i){
  61.         for (int j = i + 1; j < n; ++j){
  62.             swap(matrix[i][j], matrix[j][i]);
  63.         }
  64.     }
  65.        
  66.     for (int i = 0; i < n; ++i){
  67.         reverse(matrix[i].begin(), matrix[i].end()); //O(n)
  68.     }
  69. }
  70.  
  71. void print_matrix(const vector<vector<int>>& matrix) {
  72.     for (auto& row : matrix) { // const, auto, & || const-> no se pueda modificar | auto = vector<int> | & = ref
  73.         for (auto i : row) {
  74.             cout << i << " ";
  75.         }
  76.         cout << endl;
  77.     }
  78. }
  79.  
  80. int main(){
  81.    
  82.     vector<vector<int>> matrix_1 =
  83.     {{1, 2, 3, 4},
  84.     {5, 6, 7, 8},
  85.     {9, 10, 11, 12},
  86.     {13, 14, 15, 16}};
  87.    
  88.     vector<vector<int>> matrix_2 =
  89.     {{1, 2, 3, 4, 101},
  90.     {5, 6, 7, 8, 102},
  91.     {9, 10, 11, 12, 103},
  92.     {13, 14, 15, 16, 104},
  93.     {17, 18, 19, 20, 105}};
  94.  
  95.     cout<<"---Test 1 ----"<<endl;
  96.     cout<<"Original matrix:"<<endl;
  97.     print_matrix(matrix_1);
  98.     cout<<"Rotated matrix:"<<endl;
  99.     rotate_2(matrix_1);
  100.     print_matrix(matrix_1);
  101.    
  102.     cout<<endl<<"---Test 2 ----"<<endl;
  103.     cout<<"Original matrix:"<<endl;
  104.     print_matrix(matrix_2);
  105.     cout<<"Rotated matrix:"<<endl;
  106.     rotate_2(matrix_2);
  107.     print_matrix(matrix_2);
  108.    
  109.     return 0;
  110. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top