数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的螺旋矩阵 III
假设我们有一个具有 R 行和 C 列的二维网格，我们从 (r0, c0) 开始，面向东方。这里，网格的西北角位于第一行和第一列，网格的东南角位于最后一行和最后一列。我们将以顺时针螺旋形行走以访问此网格中的每个位置。当我们在网格边界之外时，我们继续在网格外部行走（但以后可能会返回网格边界）。我们必须找到一个坐标列表，表示按访问顺序排列的网格位置。因此，如果网格如下所示：
那么箭头将是路径。
为了解决这个问题，我们将遵循以下步骤：
创建 dirr := [[0,1],[1,0],[0,-1],[-1,0]]
创建一个矩阵 ret，len := 0，dir := 0
将 (r0, c0) 插入 ret
当 ret 的大小 < R*C 时
如果 dir = 0 或 dir = 2，则将 len 增加 1
对于范围 0 到 len – 1 中的 i
r0 := r0 + dirr[dir, 0]，c0 := c0 + dirr[dir, 1]
如果 r0 在 0 到 R 的范围内，并且 c0 在 0 到 C 的范围内，则进行下一次迭代
将 (r0, c0) 插入 ret
dir := (dir + 1) mod 4
返回 ret
让我们看看以下实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
int dirr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
public:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
vector < vector <int> > ret;
int len = 0;
int dir = 0;
ret.push_back({r0, c0});
while(ret.size() < R * C){
if(dir == 0 || dir == 2) len++;
for(int i = 0; i < len; i++){
r0 = r0 + dirr[dir][0];
c0 = c0 + dirr[dir][1];
if(r0 < 0 || c0 < 0 || c0 >= C || r0 >= R) continue;
ret.push_back({r0, c0});
}
dir = (dir + 1) % 4;
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.spiralMatrixIII(5,5,1,3));
}输入
5 5 1 3
输出
[[1,3],[1,4],[2,4],[2,3],[2,2],[1,2],[0,2],[0,3],[0,4],[3,4],[3,3],[3,2],[3,1],[2,1],[1,1],[0,1],[4,4],[4,3],[4,2],[4,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
更新于： 2020年4月30日
341 次查看
广告