题目链接：https://leetcode-cn.com/problems/cyclically-rotating-a-grid/
给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。矩阵由若干层组成，如下图所示，每种颜色代表一层：
矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：
返回执行 k 次循环轮转操作后的矩阵。
输入: grid = [[40,10],[30,20]], k = 1
输出: [[10,20],[40,30]]
解释: 上图展示了矩阵在执行循环轮转操作时每一步的状态。
输入: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释: 上图展示了矩阵在执行循环轮转操作时每一步的状态。
题意很清晰，沿着矩阵边缘绕一圈，一层又一层，就跟削苹果似的，分层效果如下图：
我们令n、m为矩阵的高和宽，那么我们沿着矩阵边缘能够分成多少层呢？经过简单的计算，我们就会知道
层
数
为
：
m
i
n
（
n
,
m
）
/
2
层数为：min（n,m）/2
层数为：min（n,m）/2
题目是要让我们对每一层都进行逆时针移动k步，问我们移动k步之后矩阵是什么样子的。
观察k的取值范围，我们会发现是很大的，高达
1
0
9
10^9
109。移动
1
0
9
10^9
109步的时间复杂度是很高的，我们有什么办法能够降低时间复杂度呢？
假
如
我
们
的
这
一
层
长
度
为
l
,
需
要
逆
时
针
移
动
k
步
。
那
么
我
们
发
现
移
动
l
%
k
和
移
动
l
步
是
等
价
的
假如我们的这一层长度为l,需要逆时针移动k步。那么我们发现移动l\%k和移动l 步是等价的
假如我们的这一层长度为l,需要逆时针移动k步。那么我们发现移动l%k和移动l步是等价的
那么我们只需要求这一层的长度
l
l
l，移动
l
%
k
l\%k
l%k步就可以了。我们假设
l
e
f
t
、
r
i
g
h
t
、
t
o
p
、
b
o
t
t
o
m
left、right、top、bottom
left、right、top、bottom分别对应的是这一层的左边界、右边界、上边界、下边界，那么
l
l
l：
l
=
(
b
o
t
t
o
m
−
t
o
p
+
1
)
∗
2
+
(
r
i
g
h
t
−
l
e
f
t
−
1
)
∗
2
l=(bottom-top+1)*2+(right-left-1)*2
l=(bottom−top+1)∗2+(right−left−1)∗2
接下来我们就需要模拟逆时针先移动一步。核心代码如下：
for(int i=bottom;i>top;i--)
grid[i][left]=grid[i-1][left]; //left
grid[top][left]=top_left;
for(int j=right;j>left+1;j--)
grid[bottom][j]=grid[bottom][j-1]; // bottom
grid[bottom][left+1]=bottom_left;
for(int i=top;i<bottom-1;i++) //right
grid[i][right]=grid[i+1][right];
grid[bottom-1][right]=bottom_right;
for(int j=left+1;j<right-1;j++)//top
grid[top][j]=grid[top][j+1];
grid[top][right-1]=top_right;
class Solution {
public:
vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
int n,m;
n=grid.size();
m=grid[0].size();
int top,bottom,left,right,sum,t;
int bottom_left,bottom_right,top_left,top_right;
for(int ii=0;ii<min(n,m)/2;ii++)
{
top=ii;
bottom=n-1-ii;
left=ii;
right=m-1-ii;
sum=(bottom-top+1)*2+(right-left-1)*2;
/*if(sum==0)
{
vector<int>in;
in.push_back(1);
in.push_back(1);
in.push_back(1);
vector<vector<int>> out;
out.push_back(in);
return out;
}*/
t=k%sum;
while(t--)
{
top_left=grid[top][left+1];
bottom_left=grid[bottom][left];
bottom_right=grid[bottom][right];
top_right=grid[top][right];
for(int i=bottom;i>top;i--)
grid[i][left]=grid[i-1][left]; //left
grid[top][left]=top_left;
for(int j=right;j>left+1;j--)
grid[bottom][j]=grid[bottom][j-1]; // bottom
grid[bottom][left+1]=bottom_left;
for(int i=top;i<bottom-1;i++) //right
grid[i][right]=grid[i+1][right];
//grid[top][right-1]=top_right;
grid[bottom-1][right]=bottom_right;
for(int j=left+1;j<right-1;j++)//top
grid[top][j]=grid[top][j+1];
grid[top][right-1]=top_right;
}
}
return grid;
}
};
