CFR Educational 16 C. Magic Odd Square ( Recursive Construction )

Problem - C - Codeforces
哎呀，我寫的真是亂七八糟，但思維倒是很直覺的。注意到 N 只有奇數，所以考慮如果有 N - 2 的解，如何擴展到 N 的解。顯然就是外面多一層「囗」型的筐，接著把 N = 3 和 N = 5 拿出來觀察一下就會知道，( N + 1 ) / 2 是偶數的時候左上角是偶數，否則左上角是奇數，然後相鄰的數都是奇偶交替。

void dfs( vvi &ans, int ql, int qr, int &oc, int &ec ){
    if( ql + 1 == qr ){
        ans[ ql ][ ql ] = oc, oc += 2;
        return;
    }
    dfs( ans, ql + 1, qr - 1, oc, ec );
    for( int i = ql, z = 0; i < qr; ++i, z ^= 1 ){
        if( not z ) ans[ ql ][ i ] = ec, ec += 2;
        else ans[ ql ][ i ] = oc, oc += 2;
    }
    for( int i = ql, z = 0; i < qr; ++i, z ^= 1 ){
        if( not z ) ans[ qr - 1 ][ i ] = ec, ec += 2;
        else ans[ qr - 1 ][ i ] = oc, oc += 2;
    }
    for( int i = ql + 1, z = 1; i + 1 < qr; ++i, z ^= 1 ){
        if( not z ) ans[ i ][ ql ] = ec, ec += 2;
        else ans[ i ][ ql ] = oc, oc += 2;
    }
    for( int i = ql + 1, z = 1; i + 1 < qr; ++i, z ^= 1 ){
        if( not z ) ans[ i ][ qr - 1 ] = ec, ec += 2;
        else ans[ i ][ qr - 1 ] = oc, oc += 2;
    }
    swap( oc, ec );
}

void solve(){
    int N; cin >> N;
    vvi ans( N, vi( N ) );
    int oc = 1, ec = 2;
    dfs( ans, 0, N, oc, ec );
    for( int i = 0; i < N; ++i, cout << endl )
        for( int j = 0; j < N; ++j, cout << " " )
            cout << ans[ i ][ j ];
}