NOIP2014普及组 T3 螺旋矩阵

50pts

模拟回形矩阵，硬刚1<=n<=100

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int g[N][N];
int n, ex, ey;

void print(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++)
            printf("%d ", g[i][j]);
        puts("");
    }
}

int main(){
    cin >> n >> ex >> ey;

    int x = 1, y = 1;
    int idx = 1;
    while (idx <= (n * n)){
        while (y <= n && !g[x][y]) g[x][y++] = idx++;
        x++, y--;

        while (x <= n && !g[x][y]) g[x++][y] = idx++;
        x--, y--;

        while (y >= 1 && !g[x][y]) g[x][y--] = idx++;
        x--, y++;

        while (x >= 1 && !g[x][y]) g[x--][y] = idx++;
        x++, y++;
    }

    cout << g[ex][ey] << '\n';

    return 0;
}

100pts

分析一下，这个是一圈一圈填数字的。那么每一圈的起始很重要，只要知道目标点，在哪圈上，我就可以在那个圈上，枚举出来目标点，时间复杂度是 �(�∗4)

#include <bits/stdc++.h>

using namespace std;

int n, x, y;
int ret = 1;

int main(){
    cin >> n >> x >> y;

    int r;
    r = min(n, min(x, n - x + 1)); 
    r = min(r, min(y, n - y + 1));
    //printf("---r %d\n", r);

    int sx = 1, sy = 1;
    for (int i = 1; i < r; i++){
        int delta = n + n + (n - 2) + (n - 2);
        ret += delta, sx++, sy++;
        n -= 2;
    }

    //printf("---ret %d  n %d\n", ret, n);

    for (int j = 1; j < n; j++){
        if (sx == x && sy == y) break;
        sy++;
        ret++;
    }

    for (int i = 1; i < n; i++){
        if (sx == x && sy == y) break;
        sx++;
        ret++;
    }

    for (int j = 1; j < n; j++){
        if (sx == x && sy == y) break;
        sy--;
        ret++;
    }

    for (int i = 1; i < n; i++){
        if (sx == x && sy == y) break;
        sx--;
        ret++;
    }

    cout << ret << '\n';

    return 0;
}