# 1260. 二维网格迁移
### 题目地址（1260. 二维网格迁移）
### 题目描述
```
给你一个 n 行 m 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
每次「迁移」操作将会引发下述活动：
位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][m - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[n - 1][m - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。
示例 1：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]
示例 2：
输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
示例 3：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出：[[1,2,3],[4,5,6],[7,8,9]]
提示：
1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
```
### 前置知识
* [数组](/leetcode-solution/thinkings/basic-data-structure.md)
* 数学
### 公司
* 字节
### 模拟法
#### 思路
我们直接翻译题目，没有任何 hack 的做法。
#### 代码
```python
from copy import deepcopy
class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
n = len(grid)
m = len(grid[0])
for _ in range(k):
old = deepcopy(grid)
for i in range(n):
for j in range(m):
if j == m - 1:
grid[(i + 1) % n][0] = old[i][j]
elif i == n - 1 and j == m - 1:
grid[0][0] = old[i][j]
else:
grid[i][j + 1] = old[i][j]
return grid
```
由于是 easy，上述做法勉强可以过，我们考虑优化。
### 数学分析
#### 思路
我们仔细观察矩阵会发现，其实这样的矩阵迁移是有规律的。 如图： 
因此这个问题就转化为我们一直的一维矩阵转移问题，LeetCode 也有原题[189. 旋转数组](https://leetcode-cn.com/problems/rotate-array/)，同时我也写了一篇文章[文科生都能看懂的循环移位算法](https://lucifer.ren/blog/2019/12/11/rotate-list/)专门讨论这个，最终我们使用的是三次旋转法，相关数学证明也有写，很详细，这里不再赘述。
LeetCode 真的是喜欢换汤不换药呀 😂
#### 代码
Python 代码：
```python
#
# @lc app=leetcode.cn id=1260 lang=python3
#
# [1260] 二维网格迁移
#
# @lc code=start
class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
n = len(grid)
m = len(grid[0])
# 二维到一维
arr = [grid[i][j] for i in range(n) for j in range(m)]
# 取模，缩小k的范围，避免无意义的运算
k %= m * n
res = []
# 首尾交换法
def reverse(l, r):
while l < r:
t = arr[l]
arr[l] = arr[r]
arr[r] = t
l += 1
r -= 1
# 三次旋转
reverse(0, m * n - k - 1)
reverse(m * n - k, m * n - 1)
reverse(0, m * n - 1)
# 一维到二维
row = []
for i in range(m * n):
if i > 0 and i % m == 0:
res.append(row)
row = []
row.append(arr[i])
res.append(row)
return res
# @lc code=end
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
### 相关题目
* [189. 旋转数组](https://leetcode-cn.com/problems/rotate-array/)
### 参考
* [文科生都能看懂的循环移位算法](https://lucifer.ren/blog/2019/12/11/rotate-list/)
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/1260.shift-2d-grid.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.