একটি পজিটিভ ইন্টিজার n দেওয়া থাকলে, n×n সাইজের একটি স্পাইরাল ম্যাট্রিক্স প্রিন্ট করতে হবে শুধু O(1) এক্সট্রা স্পেস ব্যবহার করে ক্লকওয়াইজ (clockwise) দিকều।
স্পাইরাল ম্যাট্রিক্স হলো একটি ম্যাট্রিক্স যা স্পাইরালের মতো কাজ করে — বৃত্তের কেন্দ্র থেকে শুরু করে ক্লকওয়াইজ ঘুরে। টাস্ক হলো ম্যাট্রিক্সকে স্পাইরাল ফর্মে প্রিন্ট করা ২ → ৪ → ৬ → ৮ → ১০ → ১২ → ১৪ → ১৬ → ১৮ সিকোয়েন্সে।
উদাহরণ
Input: 3 Output: 18 16 14 4 2 12 6 8 10
আনলিমিটেড স্পেসে সমাধান সহজ কিন্তু এফিশিয়েন্ট নয়। সেরা প্রোগ্রাম হলো যা মেমোরি এবং টাইম দুটোই দক্ষ। চারটি লুপ (টপ, রাইট, বটম, লेफট) না ব্যবহার করে ম্যাট্রিক্সকে দুটি অংশে ভাগ করা যায়: আপার রাইট (upper right) এবং লোয়ার লেফট (lower left)।
ফর্মুলা:
- Upper right half: mat[i][j] = (n-2x)² - (i-x) - (j-x)
- Lower left half: mat[i][j] = (n-2x-2)² + (i-x) + (j-x)
নোট: এখানে ২-এর গুণফল প্রিন্ট করা হয়েছে।
অ্যালগরিদম
int spiralmatrix(int n)
START
STEP 1: DECLARE i, j, a, b, x
STEP 2: LOOP i = 0 to n-1
LOOP j = 0 to n-1
a = min(i, j)
b = min(n-1-i, n-1-j)
x = min(a, b) // layer number
IF i <= j THEN
PRINT 2 * ((n-2x)² - (i-x) - (j-x))
ELSE
PRINT 2 * ((n-2x-2)² + (i-x) + (j-x))
END LOOP
PRINT NEWLINE
END LOOP
STOP
সি প্রোগ্রাম
#include <stdio.h>
int spiralmatrix(int n) {
int i, j, a, b, x;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
a = (i < j ? i : j);
b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
x = (a < b ? a : b);
if (i <= j)
printf("%d\t", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
else
printf("%d\t", 2 * ((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
}
printf("\n");
}
}
int main() {
int n = 3;
spiralmatrix(n);
return 0;
}
আউটপুট
18 16 14 4 2 12 6 8 10
