2D Arrays

Spiral Print

 

void print(int arr[][10],int n,int m){
    //4 variables
    int startRow = 0;
    int endRow = n - 1;
    int startCol = 0;
    int endCol = m - 1;

    //Outer Loop (Traverse array boundary)
    while(startCol<= endCol and startRow <=endRow){

        //Start Row
        for(int col = startCol ; col<=endCol; col++){
            cout << arr[startRow][col]<<" ";
        }

        //End Col
        for(int row=startRow + 1;row<=endRow;row++){
            cout << arr[row][endCol]<<" ";
        }

        //End Row
        for(int col=endCol - 1; col>=startCol;col--){
            if(startRow==endRow){
                break;
            }
            cout<< arr[endRow][col]<<" ";
        }   

        //Start Col
        for(int row = endRow-1; row >=startRow + 1;row--){
            //Avoid Duplicate Printing of elements
            if(startCol==endCol){
                break;
            }
            cout<< arr[row][startCol] <<" ";
        }

        //update the variables to point to inner spiral
        startRow++;
        endRow--;
        startCol++;
        endCol--;
    }
}

행렬을 순회할 포인터 4개를 정해서 출력한다.

이 방법 말고도 좌표를 미리 설정해두고 출력하는 방법도 가능할 것 같다.

 

 

Ramu's Mango Trees

문제 링크 : https://www.iarcs.org.in/inoi/online-study-material/topics/prefix-sums-ramus-mango-trees.php

2차원 배열을 보조 배열로 나누어 생각한다.

2차원 배열 arr(x,y)가 주어지고 M(x,y)가 arr(x,y)까지의 누적합 배열이라고 할 때,

M(x,y) = M(x-1,y) + M(x,y-1) - M(x-1,y-1) + arr(x,y) 이 성립된다.

 

각 구역을 구하는 식은 다음과 같다

S1 = M(x,y)

S2 = M(N,y) - M(x,y)

S3 = M(x,N) - M(x,y)

S4 = M(N,N) - (S1 + S2 + S3)