#include <utility>
#include <vector>
#include <algorithm>
#include <iostream>
std::pair<int, int>
rotated_local_next(int i, int j, int w, int h)
{
if(j == 0) //top , special case top-right
{
return i == w-1 ? std::make_pair(i, ++j) : std::make_pair(++i, j);
}
if(i == w-1) //right, special case bottom-right
{
return j == h-1 ? std::make_pair(--i, j) : std::make_pair(i, ++j);
}
if(j == h-1) //bottom, special case bottom-left
{
return i == 0 ? std::make_pair(i, --j) : std::make_pair(--i, j);
}
if(i == 0) //left, special case top-left
{
return j == 0 ? std::make_pair(++i, j): std::make_pair(i, --j);
}
// cannot happen
throw std::exception{};
}
std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}
struct RingView
{
RingView(std::vector<std::vector<int>>& mat, int ringnumber)
: matrix(mat)
, rows(mat.size())
, cols(mat[0].size())
, ring(ringnumber)
{}
std::vector<std::vector<int>>& matrix;
int rows;
int cols;
int ring; // zero indexed
class ring_iterator : public std::iterator<std::forward_iterator_tag, int>
{
public:
ring_iterator(RingView* v = nullptr, int xpos = 0, int ypos = 0)
: view(v)
, x(xpos)
, y(ypos)
{}
ring_iterator(const ring_iterator& other) = default;
ring_iterator(ring_iterator&& other) = default;
ring_iterator& operator =(ring_iterator const&) = default;
ring_iterator& operator=(ring_iterator&&) = default;
virtual ~ring_iterator() = default;
RingView* view;
int x;
int y;
int holder;
// Forward
ring_iterator& operator++() {
auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);
x = posnext.first;
y = posnext.second;
return *this;
}
ring_iterator operator++(int) {
auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);
ring_iterator next_iter = *this;
next_iter.x = posnext.first;
next_iter.y = posnext.second;
return next_iter;
}
// equality required to test with end
bool operator==(const ring_iterator& other) const {
if(view == nullptr ){
return other.view == nullptr;
}
return view->ring == other.view->ring && x == other.x && y == other.y;
}
bool operator!=(const ring_iterator& other) const {
return !(*this == other);
}
// usually required
int& operator*() {
return view->matrix[x][y];
}
int* operator->() {
return &(view->matrix[x][y]);
}
};
ring_iterator begin()
{
return ring_iterator(this, ring, ring);
}
ring_iterator end()
{
return begin();
}
int size() const
{
return 2*(rows+cols -2) - 4 * ring;
}
};
using Matrix = std::vector<std::vector<int>>;
void rotate_mat (Matrix &mat, int r){
auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
for(auto ring_i=0; ring_i<n_rings; ++ring_i){
RingView view(mat,ring_i);
int r_modulo = (r % view.size() + view.size()) % view.size();
auto next_location = view.begin();
std::advance(next_location, r_modulo);
std::rotate(view.begin(),next_location,view.end());
}
}
void print_matrix(Matrix &mat){
for (auto& i : mat){
for (auto& j : i) {
std::cout << j << " ";
}
std::cout << "\n";
}
std::cout << "\n";
};
int main() {
std::vector<std::vector<int>> data = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}, {17, 18, 19, 20} };
print_matrix(data);
rotate_mat(data, -2);
print_matrix(data);
return 0;
}
I2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCnN0ZDo6cGFpcjxpbnQsIGludD4Kcm90YXRlZF9sb2NhbF9uZXh0KGludCBpLCBpbnQgaiwgaW50IHcsIGludCBoKQp7CiAgIGlmKGogPT0gMCkgLy90b3AgLCBzcGVjaWFsIGNhc2UgdG9wLXJpZ2h0CiAgIHsKICAgICAgICByZXR1cm4gaSA9PSB3LTEgPyBzdGQ6Om1ha2VfcGFpcihpLCArK2opIDogc3RkOjptYWtlX3BhaXIoKytpLCBqKTsKICAgfQogICBpZihpID09IHctMSkgLy9yaWdodCwgc3BlY2lhbCBjYXNlIGJvdHRvbS1yaWdodAogICB7CiAgICAgICAgcmV0dXJuIGogPT0gaC0xID8gc3RkOjptYWtlX3BhaXIoLS1pLCBqKSA6IHN0ZDo6bWFrZV9wYWlyKGksICsraik7CiAgIH0KICAgaWYoaiA9PSBoLTEpIC8vYm90dG9tLCBzcGVjaWFsIGNhc2UgYm90dG9tLWxlZnQKICAgewogICAgICAgIHJldHVybiBpID09IDAgPyBzdGQ6Om1ha2VfcGFpcihpLCAtLWopIDogc3RkOjptYWtlX3BhaXIoLS1pLCBqKTsKICAgfQogICBpZihpID09IDApIC8vbGVmdCwgc3BlY2lhbCBjYXNlIHRvcC1sZWZ0CiAgIHsKICAgICAgICByZXR1cm4gaiA9PSAwID8gc3RkOjptYWtlX3BhaXIoKytpLCBqKTogc3RkOjptYWtlX3BhaXIoaSwgLS1qKTsKICAgfQoKICAgLy8gY2Fubm90IGhhcHBlbgogICB0aHJvdyBzdGQ6OmV4Y2VwdGlvbnt9Owp9CgpzdGQ6OnBhaXI8aW50LCBpbnQ+CnJvdGF0ZWRfbWF0cml4X25leHQoaW50IHgsIGludCB5LCBpbnQgcmluZ19pLCBpbnQgaGVpZ2h0LCBpbnQgd2lkdGggKQp7CiAgICAgYXV0byBsb2NhbF9wb2ludCA9IHJvdGF0ZWRfbG9jYWxfbmV4dCh4LXJpbmdfaSwgeS1yaW5nX2ksIHdpZHRoLTIqKHJpbmdfaSksIGhlaWdodC0yKihyaW5nX2kpKTsKICAgICByZXR1cm4gc3RkOjptYWtlX3BhaXIobG9jYWxfcG9pbnQuZmlyc3QgKyByaW5nX2ksIGxvY2FsX3BvaW50LnNlY29uZCArIHJpbmdfaSk7Cn0KCnN0cnVjdCBSaW5nVmlldwp7CiAgIFJpbmdWaWV3KHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+JiBtYXQsIGludCByaW5nbnVtYmVyKQogICA6IG1hdHJpeChtYXQpCiAgICwgcm93cyhtYXQuc2l6ZSgpKQogICAsIGNvbHMobWF0WzBdLnNpemUoKSkKICAgLCByaW5nKHJpbmdudW1iZXIpCiAgIHt9CgogICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxpbnQ+PiYgbWF0cml4OwogICBpbnQgcm93czsKICAgaW50IGNvbHM7CiAgIGludCByaW5nOyAvLyB6ZXJvIGluZGV4ZWQKCiAgICBjbGFzcyByaW5nX2l0ZXJhdG9yIDogcHVibGljIHN0ZDo6aXRlcmF0b3I8c3RkOjpmb3J3YXJkX2l0ZXJhdG9yX3RhZywgaW50PgogICAgewogICAgcHVibGljOgoKICAgICAgICByaW5nX2l0ZXJhdG9yKFJpbmdWaWV3KiB2ID0gbnVsbHB0ciwgaW50IHhwb3MgPSAwLCBpbnQgeXBvcyA9IDApCiAgICAgICAgOiB2aWV3KHYpCiAgICAgICAgLCB4KHhwb3MpCiAgICAgICAgLCB5KHlwb3MpCiAgICAgICAge30KCiAgICAgICAgcmluZ19pdGVyYXRvcihjb25zdCByaW5nX2l0ZXJhdG9yJiBvdGhlcikgPSBkZWZhdWx0OwogICAgICAgIHJpbmdfaXRlcmF0b3IocmluZ19pdGVyYXRvciYmIG90aGVyKSA9IGRlZmF1bHQ7CiAgICAgICAgcmluZ19pdGVyYXRvciYgb3BlcmF0b3IgPShyaW5nX2l0ZXJhdG9yIGNvbnN0JikgPSBkZWZhdWx0OwogICAgICAgIHJpbmdfaXRlcmF0b3ImIG9wZXJhdG9yPShyaW5nX2l0ZXJhdG9yJiYpID0gZGVmYXVsdDsKICAgICAgICB2aXJ0dWFsIH5yaW5nX2l0ZXJhdG9yKCkgPSBkZWZhdWx0OwoKICAgICAgICBSaW5nVmlldyogdmlldzsKICAgICAgICBpbnQgeDsKICAgICAgICBpbnQgeTsKICAgICAgICBpbnQgaG9sZGVyOwoKICAgICAgICAvLyBGb3J3YXJkCiAgICAgICAgcmluZ19pdGVyYXRvciYgb3BlcmF0b3IrKygpIHsKICAgICAgICAgICAgYXV0byBwb3NuZXh0ID0gcm90YXRlZF9tYXRyaXhfbmV4dCh4LCB5LCB2aWV3LT5yaW5nLCB2aWV3LT5jb2xzLCB2aWV3LT5yb3dzKTsKCiAgICAgICAgICAgIHggPSBwb3NuZXh0LmZpcnN0OwogICAgICAgICAgICB5ID0gcG9zbmV4dC5zZWNvbmQ7CiAgICAgICAgICAgIHJldHVybiAqdGhpczsKICAgICAgICB9CgogICAgICAgIHJpbmdfaXRlcmF0b3Igb3BlcmF0b3IrKyhpbnQpIHsKICAgICAgICAgICAgYXV0byBwb3NuZXh0ID0gcm90YXRlZF9tYXRyaXhfbmV4dCh4LCB5LCB2aWV3LT5yaW5nLCB2aWV3LT5jb2xzLCB2aWV3LT5yb3dzKTsKICAgICAgICAgICAgcmluZ19pdGVyYXRvciBuZXh0X2l0ZXIgPSAqdGhpczsKICAgICAgICAgICAgbmV4dF9pdGVyLnggPSBwb3NuZXh0LmZpcnN0OwogICAgICAgICAgICBuZXh0X2l0ZXIueSA9IHBvc25leHQuc2Vjb25kOwogICAgICAgICAgICByZXR1cm4gbmV4dF9pdGVyOwogICAgICAgIH0KCiAgICAgICAgLy8gZXF1YWxpdHkgcmVxdWlyZWQgdG8gdGVzdCB3aXRoIGVuZAogICAgICAgIGJvb2wgb3BlcmF0b3I9PShjb25zdCByaW5nX2l0ZXJhdG9yJiBvdGhlcikgY29uc3QgewogICAgICAgICAgICBpZih2aWV3ID09IG51bGxwdHIgKXsKICAgICAgICAgICAgICAgIHJldHVybiBvdGhlci52aWV3ID09IG51bGxwdHI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIHZpZXctPnJpbmcgPT0gb3RoZXIudmlldy0+cmluZyAmJiB4ID09IG90aGVyLnggJiYgeSA9PSBvdGhlci55OwogICAgICAgIH0KCiAgICAgICAgYm9vbCBvcGVyYXRvciE9KGNvbnN0IHJpbmdfaXRlcmF0b3ImIG90aGVyKSBjb25zdCB7CiAgICAgICAgICAgIHJldHVybiAhKCp0aGlzID09IG90aGVyKTsKICAgICAgICB9CgogICAgICAgIC8vIHVzdWFsbHkgcmVxdWlyZWQKICAgICAgICBpbnQmIG9wZXJhdG9yKigpIHsKICAgICAgICAgICAgcmV0dXJuIHZpZXctPm1hdHJpeFt4XVt5XTsKICAgICAgICB9CiAgICAgICAgaW50KiBvcGVyYXRvci0+KCkgewogICAgICAgICAgICByZXR1cm4gJih2aWV3LT5tYXRyaXhbeF1beV0pOwogICAgICAgIH0KICAgIH07CgogICAgcmluZ19pdGVyYXRvciBiZWdpbigpCiAgICB7CiAgICAgICAgcmV0dXJuIHJpbmdfaXRlcmF0b3IodGhpcywgcmluZywgcmluZyk7CiAgICB9CgogICAgcmluZ19pdGVyYXRvciBlbmQoKQogICAgewogICAgICAgIHJldHVybiBiZWdpbigpOwogICAgfQoKICAgIGludCBzaXplKCkgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gMioocm93cytjb2xzIC0yKSAtIDQgKiByaW5nOwogICAgfQp9OwoKdXNpbmcgTWF0cml4ID0gc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj47Cgp2b2lkIHJvdGF0ZV9tYXQgKE1hdHJpeCAmbWF0LCBpbnQgcil7CiAgICBhdXRvIG5fcmluZ3MgPSBzdGQ6Om1pbihtYXQuc2l6ZSgpLG1hdFswXS5zaXplKCkpLzI7IC8vIE51bWJlciBvZiByaW5ncwogICAgZm9yKGF1dG8gcmluZ19pPTA7IHJpbmdfaTxuX3JpbmdzOyArK3JpbmdfaSl7CiAgICAgICAgUmluZ1ZpZXcgdmlldyhtYXQscmluZ19pKTsKICAgICAgICBpbnQgcl9tb2R1bG8gPSAociAlIHZpZXcuc2l6ZSgpICsgdmlldy5zaXplKCkpICUgdmlldy5zaXplKCk7CiAgICAgICAgYXV0byBuZXh0X2xvY2F0aW9uID0gdmlldy5iZWdpbigpOwogICAgICAgIHN0ZDo6YWR2YW5jZShuZXh0X2xvY2F0aW9uLCByX21vZHVsbyk7CiAgICAgICAgc3RkOjpyb3RhdGUodmlldy5iZWdpbigpLG5leHRfbG9jYXRpb24sdmlldy5lbmQoKSk7CiAgICB9Cn0KCnZvaWQgcHJpbnRfbWF0cml4KE1hdHJpeCAmbWF0KXsKICAgIGZvciAoYXV0byYgaSA6IG1hdCl7CiAgICAgICAgZm9yIChhdXRvJiBqIDogaSkgewogICAgICAgICAgICBzdGQ6OmNvdXQgPDwgaiA8PCAiICI7CiAgICAgICAgfQogICAgICAgIHN0ZDo6Y291dCA8PCAiXG4iOwogICAgfQogICAgc3RkOjpjb3V0IDw8ICJcbiI7Cn07CgppbnQgbWFpbigpIHsKICAgIHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+IGRhdGEgPSB7IHsxLDIsMyw0fSwgezUsNiw3LDh9LCB7OSwxMCwxMSwxMn0sIHsxMywxNCwxNSwxNn0sIHsxNywgMTgsIDE5LCAyMH0gfTsKICAgIHByaW50X21hdHJpeChkYXRhKTsKICAgIHJvdGF0ZV9tYXQoZGF0YSwgLTIpOwogICAgcHJpbnRfbWF0cml4KGRhdGEpOwogICAgcmV0dXJuIDA7Cn0=