1914

1914. Cyclically Rotating a Grid (Medium)

You are given an m x n integer matrix grid​​​, where m and n are both even integers, and an integer k.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:

A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below:

Return the matrix after applying k cyclic rotations to it.

 

Example 1:

Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.

Example 2:

Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• Both m and n are even integers.
• 1 <= grid[i][j] <= 5000
• 1 <= k <= 109

Related Topics:
Array

Solution 1.

The rotate function comes from 189. Rotate Array (Medium).

// OJ: https://leetcode.com/problems/cyclically-rotating-a-grid/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(M + N)
class Solution {
    void rotate(vector<int>& A, int k) {
        int cnt = 0, N = A.size();
        k %= N;
        if (k == 0) return;
        for (int i = 0; cnt < N; ++i) {
            int j = i, tmp = A[j];
            do {
                int t = (j + k) % N, next = A[t];
                A[t] = tmp;
                tmp = next;
                j = t;
                ++cnt;
            } while (j != i);
        }
    }
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& A, int K) {
        int M = A.size(), N = A[0].size();
        for (int i = 0; i < min(M, N) / 2; ++i) {
            int x = i, y = i, h = M - 2 * i, w = N - 2 * i, k = 0, len = 2 * (h + w - 2);
            vector<int> v(len);
            for (int j = 1; j < w; ++j, ++y) v[k++] = A[x][y];
            for (int j = 1; j < h; ++j, ++x) v[k++] = A[x][y];
            for (int j = 1; j < w; ++j, --y) v[k++] = A[x][y];
            for (int j = 1; j < h; ++j, --x) v[k++] = A[x][y];
            rotate(v, len - K % len);
            x = i, y = i, k = 0;
            for (int j = 1; j < w; ++j, ++y) A[x][y] = v[k++];
            for (int j = 1; j < h; ++j, ++x) A[x][y] = v[k++];
            for (int j = 1; j < w; ++j, --y) A[x][y] = v[k++];
            for (int j = 1; j < h; ++j, --x) A[x][y] = v[k++] ;
        }
        return A;
    }
};