ACM 蛇形填数

蛇形填数

时间限制：3000 ms  |  内存限制：65535 KB

难度：3

 

描述

在n*n方陈里填入1,2,...,n*n,要求填成蛇形。例如n=4时方陈为：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4

 

输入

直接输入方陈的维数，即n的值。(n<=100)

输出

输出结果是蛇形方陈。

样例输入

3

样例输出

7 8 1
6 9 2
5 4 3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int dx[] = {1,  0, -1, 0};
const int dy[] = {0, -1,  0, 1};

int main(){
    int n;
    cin >> n;
    vector<vector<int> > matrix(n+2,vector<int>(n+2,0));
    for (int i = 0; i < n+2;  ++ i) {
        matrix[0][i] = matrix[n+1][i] = 1;
        matrix[i][0] = matrix[i][n+1] = 1;
    }
    int step = 0, x = 0, y = n, cnt = 0;
    while(cnt !=n*n){
        step %=4;
        while(matrix[x+dx[step]][y+dy[step]] == 0){
            x +=dx[step];
            y +=dy[step];
            matrix[x][y] = ++cnt;
        }
        step++;
    }
    
    for (int i = 1; i <= n; ++ i) {
        cout<<matrix[i][1];
        for(int j = 2; j <=n; ++ j)
            cout<<" "<<matrix[i][j];
        cout<<endl;
    }
}