Grade 12 · Baccalaureate exam reviewCitește în română

Matrix: concentric borders

Original: Matrice — contururi concentrice

O(n²)C++1759 lines2 examples

The idea

The task (exam part III.2 style): n is read (2 ≤ n ≤ 20). Build in memory a matrix with n rows and n columns in which the elements on the outer border are 1, those on the next border 2 and so on, then print it. Instead of 'drawing' border after border, we notice that the element (i, j) (numbered from 0) lies on the border given by its distance to the nearest edge: min(i, j, n-1-i, n-1-j) + 1. This way every element is computed directly, exactly once.

Original description (Romanian)

Cerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți în memorie o matrice cu n linii și n coloane în care elementele de pe conturul exterior sunt 1, cele de pe conturul următor 2 și așa mai departe, apoi afișați-o. În loc să „desenăm” contur după contur, observăm că elementul (i, j) (numerotare de la 0) se află pe conturul dat de distanța lui până la cea mai apropiată margine: min(i, j, n-1-i, n-1-j) + 1. Așa fiecare element se calculează direct, o singură dată.

Complexity
O(n^2)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

5

Expected output

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
Example 2

Input

4

Expected output

1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

matrice-contururi-concentrice.cpp
/*
 * Titlu: Matrice — contururi concentrice
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți
 *            în memorie o matrice cu n linii și n coloane în care elementele de pe
 *            conturul exterior sunt 1, cele de pe conturul următor 2 și așa mai
 *            departe, apoi afișați-o. În loc să „desenăm” contur după contur,
 *            observăm că elementul (i, j) (numerotare de la 0) se află pe conturul
 *            dat de distanța lui până la cea mai apropiată margine:
 *            min(i, j, n-1-i, n-1-j) + 1. Așa fiecare element se calculează
 *            direct, o singură dată.
 * Complexitate: O(n^2)
 *
 * Exemplu
 * Intrare: 5
 * Ieșire:
 * 1 1 1 1 1
 * 1 2 2 2 1
 * 1 2 3 2 1
 * 1 2 2 2 1
 * 1 1 1 1 1
 *
 * Exemplu
 * Intrare: 4
 * Ieșire:
 * 1 1 1 1
 * 1 2 2 1
 * 1 2 2 1
 * 1 1 1 1
 */
#include <iostream>
using namespace std;

int main()
{
    int n, a[20][20];
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            int d = i;
            if (j < d)
                d = j;
            if (n - 1 - i < d)
                d = n - 1 - i;
            if (n - 1 - j < d)
                d = n - 1 - j;
            a[i][j] = d + 1;
        }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.