Районная олимпиада по информатике. 2008-2009 учебный год.

Задача E. Спираль

Ограничение по времени:

2 seconds

Ограничение по памяти:

64 megabytes

Спираль размера $N$ – это таблица натуральных чисел размером $N$x$N$, в центре таблицы всегда 1, справа от нее 2, спираль закручивается против часовой стрелки. Выведите спираль размера $N$.

Формат входного файла

Единственная строка входного файла содержит одно число – $N$ ($1 <= N < 100$, $N$ - нечетное).

Формат выходного файла

Выведите $N$ строк по $N$ чисел – спираль размера $N$. Числа в строках должны быть разделены пробелами.

Примеры:

Вход

1

Ответ

1

Вход

3

Ответ

5 4 3
6 1 2
7 8 9

Вход

5

Ответ

17 16 15 14 13
18  5  4  3 12
19  6  1  2 11
20  7  8  9 10
21 22 23 24 25

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int x[n+1][n+1];
    x[(n+1)/2][(n+1)/2] = 1;
    for (int l=2; l<=(n+1)/2; l++) {
        int a = (n+1)/2 + l - 1, b = (n+1)/2 - l + 1;
        x[a][b+1] = x[a-1][b+1] + 1;
        for (int j=b+2; j<=a; j++) {
            x[a][j] = x[a][j-1] + 1;
        }
        for (int i=a-1; i>=b; i--) {
            x[i][a] = x[i+1][a] + 1;
        }
        for (int j=a-1; j>=b; j--) {
            x[b][j] = x[b][j+1] + 1;
        }
        for (int i=b+1; i<=a; i++) {
            x[i][b] = x[i-1][b] + 1;
        }
    }
    for (int j=n; j>=1; j--) {
        for (int i=1; i<=n; i++) {
            cout << x[i][j] << ' ';
        }
        cout << '\n';
    }
}

показать/скрыть код

void solve() {

cin >> n;

vector<vector<ll>> v(n, vector<ll>(n, 0));

ll nums = n * n, l_start = 0, l_end = n - 1, r_start = 0, r_end = n - 1;

while (nums >= 1) {

for (int i = r_end; i >= r_start; i -= 1) {

v[l_end][i] = nums;

nums -= 1;

}

l_end -= 1;

for (int i = l_end; i >= l_start; i -= 1) {

v[i][r_start] = nums;

nums -= 1;

}

r_start += 1;

for (int i = r_start; i <= r_end; i += 1) {

v[l_start][i] = nums;

nums -= 1;

}

l_start += 1;

for (int i = l_start; i <= l_end; i += 1) {

v[i][r_end] = nums;

nums -= 1;

}

r_end -= 1;

}

show(v);

}