เกลียวเมทริกซ์ III ใน C++

สมมติว่าเรามีตาราง 2 มิติที่มีแถว R และคอลัมน์ C เราเริ่มจาก (r0, c0) ที่หันไปทางทิศตะวันออก ที่นี่ มุมตะวันตกเฉียงเหนือของตารางอยู่ที่แถวและคอลัมน์แรก และมุมตะวันออกเฉียงใต้ของตารางอยู่ที่แถวและคอลัมน์สุดท้าย เราจะเดินเป็นเกลียวตามเข็มนาฬิกาเพื่อเยี่ยมชมทุกตำแหน่งในตารางนี้ เมื่อเราอยู่ที่นอกเขตกริด เราจะเดินต่อไปนอกกริด (แต่อาจกลับสู่ขอบเขตกริดในภายหลัง) เราต้องหารายชื่อพิกัดที่แสดงถึงตำแหน่งของกริดตามลำดับที่เข้าเยี่ยมชม ดังนั้นหากกริดเป็นเหมือน −

จากนั้นลูกศรจะเป็นเส้นทาง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้าง dirr :=[[0,1],[1,0],[0,-1,[-1,0]]

• สร้างเมทริกซ์ ret, len :=0, dir :=0

• แทรก (r0, c0) ลงใน ret

• ในขณะที่ขนาดของ ret

  • ถ้า dir =0 หรือ dir =2 ให้เพิ่ม len ขึ้น 1

  • สำหรับฉันอยู่ในช่วง 0 ถึงเลน – 1

    • r0 :=r0 + dirr[dir, 0], c0 :=c0 + dirr[dir, 1]

    • ถ้า r0 อยู่ในช่วง 0 ถึง R และ c0 ในช่วง 0 ถึง C ให้ทำซ้ำต่อไป

    • แทรก (r0, c0) ลงใน ret

  • dir :=(dir + 1) mod 4

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;void print_vector(vector> v){ cout <<"["; for(int i =0; i> spiralMatrixIII (int R, int C, int r0, int c0) { vector > ret; int len ​​=0; int dir =0; ret.push_back({r0, c0}); ในขณะที่(ret.size() =C || r0>=R) ดำเนินการต่อ; ret.push_back({r0, c0}); } dir =(dir + 1) % 4; } ผลตอบแทนย้อนหลัง; }};main(){ โซลูชัน ob; print_vector(ob.spiralMatrixIII(5,5,1,3));}

อินพุต

5513

ผลลัพธ์