CODEWITHSUNDEEP
c++algorithmmatrixrotation
erip
erip

Reputation: 16935

How do I rotate M x N matrix 180 degrees in place?

I've seen several questions here that don't quite answer my question. I'm trying to do a rendition of the classic matrix rotation question used so often in interview questions. Instead of focusing on the square matrix, I'm interested in M x N matrices.

For input matrix

1 2 3
4 5 6
7 8 9
1 2 3

I'd like to transform the matrix into 

3 2 1
9 8 7
6 5 4
3 2 1

Here is the code I've written:

#include <iostream>
#include <vector>
#include <algorithm>

void do_swaps(int& a, int& b, int& c, int& d) {
  std::swap(a, b);
  std::swap(c, d);
}

void rotate(std::vector<std::vector<int>>& v) {
  size_t m = v.size();
  size_t n = v[0].size();

  for(size_t i = 0; i < m/2; ++i) {
    for(size_t j = 0; j <= n/2; ++j) {
      do_swaps(v[i][j], v[m-i-1][n-j-1], v[m-j-1][i], v[j][n-i-1]);
    }
  }
}

void print(const std::vector<std::vector<int>>& v) {
  size_t m = v.size();
  size_t n = v[0].size();

  for(size_t i = 0; i < m; ++i) {
    for(size_t j = 0; j < n; ++j) {
      std::cout << v[i][j] << ' ';
    }
    std::cout << '\n';
  }
}


int main() {
  std::vector<std::vector<int>> m{{1,2,3}, {4,5,6}, {7,8,9}, {1, 2, 3}};
  std::cout << "Before: \n";
  print(m);
  rotate(m);
  std::cout << "\nAfter: \n";
  print(m);
}

And here's my output:

Before: 
1 2 3 
4 5 6 
7 8 9 
1 2 3 

After: 
3 2 1 
9 5 7 
6 8 4 
3 2 1

My code works for 3 x 3 matrices (haven't tested higher dimensional matrices), but I seem to have an off by one error in my code causing the inner-most elements to remain unswapped.

In the line for(size_t j = 0; j <= n/2; ++j) {, I've tried adjusting the stop condition to several things including j < (n+1)/2; and j < (n-1)/2;, but it remains the same.

Can someone explain where I've gone wrong in my algorithm?

Upvotes: 0

Views: 3687

Answers (3)

Jaro
Jaro

Reputation: 873

A pythonish way (not in place):

d = (1, 2, 3), (4, 5, 6), (7, 8, 9), (1, 2, 3)

[r[::-1] for r in d[::-1]]

Upvotes: 2

hedgie
hedgie

Reputation: 71

You don't take care of middle line in case when lines number is odd.

Further, you swap elements that lie on the middle column (when columns number is odd) twice. You can check if m is odd with a bitwise-and with 1.

The following is an easier way to project swapped values is presented above and you don't even have to care about the middle column in this case.

void rotate(std::vector<std::vector<int>>& v) {
    size_t m = v.size();
    size_t n = v[0].size();

    for (size_t i = 0; i < m / 2; ++i)
    {
        for (size_t j = 0; j < n; ++j)
            std::swap(v[i][j], v[m - i - 1][n - j - 1]);
    }
    if (m&1)
    for (size_t i = 0; i< n/2; ++i)
        std::swap(v[m/2][i], v[m/2][n-i-1]);
}

Upvotes: 3

Spektre
Spektre

Reputation: 51835

I would use mirror x and then mirror y or vice versa. It is in-place and safe for any resolution (even/odd). So first swap all rows and then all columns (or vice versa). Here some code for this. 

void rotate(std::vector<std::vector<int>>& v) {
  size_t m= v.size();
  size_t n=v[0].size();

  for(size_t i=0;i<m;i++) { 
    for(size_t j=0,k=n-1;j<k;j++,k--) {
        std::swap(v[i][j],v[i][k]); 
    }
  }

  for(size_t j=0;j<n;j++) { 
    for(size_t i=0, k=m-1; i<k; i++, k--) {
      std::swap(v[i][j],v[k][j]);    
    }
  }
}

Upvotes: 2

Related Questions