Cho lưới R x C, bắt đầu từ (r0, c0) hướng Đông. Đi theo xoắn ốc chiều kim đồng hồ, có thể ra ngoài lưới nhưng vẫn tính bước. Trả về danh sách tọa độ ô lưới theo thứ tự ghé thăm.
Ví dụ: R=5, C=5, r0=1, c0=3 → 25 tọa độ theo thứ tự xoắn ốc.
Giải pháp:
Hướng: dirr = [[0,1],[1,0],[0,-1],[-1,0]] (Đông, Nam, Tây, Bắc)
len=0, dir=0, ret=[(r0,c0)]
While ret.size < R*C:
Nếu dir=0 hoặc 2: len++
Lặp len lần: r0+=dirr[dir][0], c0+=dirr[dir][1]
Nếu trong lưới: thêm vào ret
dir = (dir+1)%4Trả về ret
Ví dụ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<int>> v){ cout << "["; for(auto &r : v){ cout << "["; for(int x : r) cout << x << ", "; 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, 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+=dirr[dir][0]; c0+=dirr[dir][1]; if(r0<0||c0<0||r0>=R||c0>=C) continue; ret.push_back({r0,c0}); } dir = (dir+1)%4; } return ret; } }; int main(){ Solution ob; print_vector(ob.spiralMatrixIII(5,5,1,3)); }Đầu vào
5 5 1 3
Đầu ra
[[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]]