Alqoritm

Spiral Matrix – saat əqrəbi və əksi istiqamətində (ardı)

spiral-matrix
Written by Mushfiq Mammadov

Bundan əvvəlki yazıda qeyd etmişdim ki, Spiral Matrix ilə bağlı yazdığım kod bəyənilməmişdi. Səbəb isə o idi ki, for dövründən çox istifadə edilmişdi. Belə başa düşdüm ki, bu tapşırığı bir for dövrü ilə də həll etmək mümkündür. Ona görə də internetdə əlavə araşdırma etməyə başladım.

Bu mövzu ilə bağlı bir xeyli yazı oxudum, araşdırma elədim. Gəldiyim qənaət isə belə oldu ki, spiral matrix alqoritminin işləməsində əsas 2 qanunauyğunluq var (saat əqrəbi istiqamətində):

  1. istiqamət üzrə – “sağ -> aşağı -> sol -> yuxarı" təkrarlanır;
  2. addımlar üzrə – hər iki istiqamətdən bir gediləcək addımların sayı 1 artır, yəni 1 sağ, 1 aşağı, 2 sol, 2 yuxarı, 3 sağ, 3 aşağı, 4 sol, 4 yuxarı və s. –> 1, 1, 2, 2, 3, 3, 4, 4...

Bu qanunauyğunluqdan yola çıxaraq nəhayət ki, ancaq bir for dövründən istifadə etməklə tapşırığı həll edə bildim. Daha anlaşıqlı olsun deyə kodda istifadə edilən bəzi dəyişənlərin şərhini aşağıda qeyd etmişəm:

direction – istiqaməti bildirir, 0 – sağ, 1 – aşağı, 2 – sol, 3 – yuxarı;
steps – cari istiqamət üzrə (direction) gediləcək addımların sayı;
currentStep – ümumi addımlar içərisindən (steps) cari addımın nömrəsini bildirir, cari istiqamət üzrə gediləcək addımların bitib-bitməməsini yoxlamaq üçün istifadə edilir;
change – istiqamətin dəyişib dəyişmədiyini yoxlayır, hər 2 istiqamət dəyişikliyindən sonra addımların sayını (steps) bir artırmaq üçün istifadə edilir.

package az.mm.spiralmatrix;

import java.util.Scanner;

/**
 * @author MM <[email protected]>
 */
public class Main3 {
    private static int row, col, matrix[][];
    private static boolean isClockwise = true;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter matrix lengths (example 4 3):");
        row = sc.nextInt();
        col = sc.nextInt();
        createMatrix();
        printSpiralElements();
    }
 
    private static void printSpiralElements(){
        System.out.println(isClockwise ? "Clockwise:" : "Counter-Clockwise");
        int i = row%2 == 0 ? row/2-1 : row/2;
        int j = isClockwise ? col%2 == 0 ? col/2-1 : col/2 : col/2;
        int direction=0, steps=1, currentStep=0, change=0; 
 
        for (int a = 0; a < row*col; a++){
            if (i<0 || i>=row || j<0 || j>=col) break; //kvadrat olmayan matrislər üçün bu şərt vacibdir
            System.out.print(matrix[i][j]+" ");
 
            if (currentStep < steps) 
                currentStep++;
            else {
                currentStep = 1;
                if (change == 1) steps++;
                change = (change+1) % 2;
                direction = (direction+1) % 4;
            }
            
            switch (direction){
                case 0: if(isClockwise) j++; else j--; break;
                case 1: i++; break;
                case 2: if(isClockwise) j--; else j++; break;
                case 3: i--; break;
            }
        }
    }
 
    private static void createMatrix() {
        matrix = new int[row][col];
        int value = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) 
                System.out.print((matrix[i][j] = value++) + "\t");
            System.out.println();
        }
    }
}

Output:

Please enter matrix lengths (example 4 3):
4 6
1	2	3	4	5	6	
7	8	9	10	11	12	
13	14	15	16	17	18	
19	20	21	22	23	24	
Clockwise:
9 10 16 15 14 8 2 3 4 5 11 17 23 22 21 20 19 13 7 1

Bundan sonra növbəti iki funksionallığın da əlavə edilməsi istənildi:

  1. Mərkəz nöqtəsi əgər 1-dən çoxdursa, hansı nöqtədən başlanılmasını istəyə bağlı olaraq təyin edə bilmə;
  2. Matrixin bütün elementlərinin spirala daxil edilməsi. Yəni əgər matrix kvadrat deyilsə, hələ də spirala düşməyən element qalıbsa, matrixdən çölə çıxıb yenidən içəri daxil olma. 

Qeyd etdiyim funksionallıqlar da əlavə edildikdən sonra kodun son vəziyyəti aşağıdakı kimi oldu:

package az.mm.spiralmatrix;

import java.util.Scanner;

/**
 * @author MM <[email protected]>
 */
public class Main4 {
    private static int row, col, matrix[][], maxCenter, centerN;
    private static final boolean isClockwise = false;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            System.out.println("\nPlease enter matrix lengths (example 4 3):");
            row = sc.nextInt();
            col = sc.nextInt();
            matrix = new int[row][col];
            maxCenter = (row%2==0 && col%2==0) ? 4 : (row%2==0 || col%2==0) ? 2 : 1;
            if (maxCenter != 1){ 
                System.out.println("Please enter center element number: 1 - " + maxCenter);
                centerN = sc.nextInt();
            }
            start();
        }
    }
 
    private static void start(){
        System.out.println(isClockwise ? "Clockwise:" : "Counter-Clockwise");
        int i=row/2, j=col/2;
        if(maxCenter > 1){ 
            if((row%2 == 0 && centerN==1) || (maxCenter>2 && centerN==2)) i=row/2-1; 
            if((col%2 == 0 && centerN==1) || (maxCenter>2 && centerN==3)) j=col/2-1;
        }
        int direction=0, steps=1, currentStep=0, change=0; 
 
        for (int a = 1; a <= row*col; a++){
            if (i<0 || i>=row || j<0 || j>=col) a--;        
            else matrix[i][j] = a;
            
            if (currentStep < steps) 
                currentStep++;
            else {
                currentStep = 1;
                if (change == 1) steps++;
                change = (change+1) % 2;
                direction = (direction+1) % 4;
            }
            
            switch (direction){
                case 0: if(isClockwise) j++; else j--; break;
                case 1: i++; break;
                case 2: if(isClockwise) j--; else j++; break;
                case 3: i--; break;
            }
        }
        printMatrix();
    }
    
    private static void printMatrix(){
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++)
                System.out.print(matrix[i][j] + "\t");
            System.out.println();
        }
    }
}

Output:

Please enter matrix lengths (example 4 3):
6 8
Please enter center element number: 1 - 4
2
Clockwise:
48	42	21	22	23	24	25	26	
47	41	20	7	8	9	10	27	
46	40	19	6	1	2	11	28	
45	39	18	5	4	3	12	29	
44	38	17	16	15	14	13	30	
43	37	36	35	34	33	32	31

Alınan nəticəni yoxlamaq daha rahat olsun deyə kodun son versiyasında xırda dəyişiklik etdim. Son versiyada matrixin elementləri birbaşa spiral şəklində çap edilir.

Kodlara daha rahat şəkildə aşağıdakı github linkindən baxa və ya yükləyə bilərsiniz:

https://github.com/mmushfiq/SpiralMatrixConsole 

 

Bu məqalə də bu qədər. Ümid edirəm maraqlı olmuşdur 🙂

About the author

Mushfiq Mammadov