資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告