No.217 魔方陣を作ろう - yukicoder
class MakeMagicSquare
{
public:
typedef vector<vector<int>> Mat;
void report(const Mat &mat) {
int n = mat.size();
REP(i,n)
{
REP(j,n)
{
cout<<mat[i][j];
if (j < n-1)
cout<<" ";
}
cout<<endl;
}
}
Mat makeOddMS(int n) {
Mat mat(n,vector<int>(n,0));
int i,j;
i = 0;
j = n/2;
for (int k = 1; k <= n*n; ++k)
{
mat[i][j] = k;
int ii = i, jj = j;
i = (i-1+n)%n;
j = (j+1)%n;
if ( mat[i][j] > 0)
{
i = (ii+1)%n;
j = jj;
}
}
return mat;
}
Mat make4xMS(int n) {
Mat mat(n,vector<int>(n,0));
auto tmp(mat);
REP(dx,n/4)
REP(dy,n/4)
{
int x = 4*dx;
int y = 4*dy;
REP(i,4)
{
tmp[x+i][y+i] = 1;
tmp[x+i][(4+y)-1-i] = 1;
}
}
int x,y;
x = y = 0;
for (int k = 1; k <= n*n; ++k)
{
if ( tmp[y][x] )
mat[y][x] = k;
++x;
if ( x == n )
{
++y;
x = 0;
}
}
x = y = n-1;
for (int k = 1; k <= n*n; ++k)
{
if ( !tmp[y][x] )
mat[y][x] = k;
--x;
if ( x < 0 )
{
--y;
x = n-1;
}
}
return mat;
}
Mat LUX(int n) {
int m = n/2;
auto small = makeOddMS(m);
REP(i,m)
REP(j,m)
small[i][j] = 4*(small[i][j]-1);
vector<vector<char>> lux(m,vector<char>(m,'L'));
REP(i,m)
lux[m/2+1][i] = 'U';
FOR(i,m/2+2,m)
REP(j,m)
lux[i][j] = 'X';
swap(lux[m/2][m/2], lux[m/2+1][m/2]);
Mat mat(n,vector<int>(n,0));
const Mat L = {{4,1},
{2,3}};
const Mat U = {{1,4},
{2,3}};
const Mat X = {{1,4},
{3,2}};
REP(i,n)
REP(j,n)
{
int iy = i/2;
int ix = j/2;
int dy = i%2;
int dx = j%2;
switch ( lux[iy][ix] )
{
case 'L':
mat[i][j] = L[dy][dx] + small[iy][ix];
break;
case 'U':
mat[i][j] = U[dy][dx] + small[iy][ix];
break;
case 'X':
mat[i][j] = X[dy][dx] + small[iy][ix];
break;
}
}
return mat;
}
void solve(void)
{
int n;
cin>>n;
int N = n*(n*n+1)/2;
if (n % 2 == 1)
{
report(makeOddMS(n));
}
else if (n % 4 == 0)
{
report(make4xMS(n));
}
else if (n % 4 == 2)
{
report(LUX(n));
}
}
};